题目描述
在m个数中, 最多删除k个, 使得剩下序列的价值最大.
题目分析
先考虑搜索;
搜索过程就是遍历所有删除不大于K个数的情况(即不一定全选k个元素); 在所有方案中寻找最大值;
* 选择: 对于每一个元素可以删除可以不删除, 但最多只能删除k个;
* 参数: 当前考虑选择的序列下标idx, 已选择的元素cnt, 当前价值cur_ans, 保留的上一个元素last;
* 出口: idx > m;(代码见下文)
现在考虑如何将搜索代码优化成dp
* 搜索的启发: 在搜索中, 迭代到新状态, 关键还需要序列中上一个元素last, 以及上一个状态是什么(删除了哪些元素);
//即可能是保留了a[i-1],也可能是删除了a[i-1], a[i-2]....a[i-k]的其中一个
* 状态表示: dp[i][j]表示以i结尾的删除j次并保留i的序列最大受益;
- 状态转移: dp[i][j] = max(dp[i-1][j]+w[a[last[i-1][j]]][a[i]], dp[i-2][j-1] + w[a[last[i-2]]][a[i]]....);
- 这里有点绕, 反正先不看last数组, 就是考虑状态从dp[i-k-1][j-k] 转移到 dp[i][j]的最大值:
例如k = 1, 就从dp[1][2] 查看到 dp[3][3] - 初始状态: 全员初始化为0就好
算法1
(暴搜)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
int n,k,m,ans;
int w[N][N];
int a[N];
void dfs(int idx, int cnt, int cur_ans, int last){
if(idx > m){
ans = max(ans,cur_ans);
return;
}
if(cnt == k){ //删除次数已经用光,只能傻乎乎往下计算了;
dfs(idx+1,cnt, cur_ans+w[a[last]][a[idx]], idx);
}
else{ //次数还未用光,可以选择
//删除
dfs(idx+1,cnt+1, cur_ans, last);
//不删除
dfs(idx+1,cnt,cur_ans+w[a[last]][a[idx]], idx);
}
}
int main(){
cin >> n >> k >> m;
for(int i = 1; i <= m; i++) cin>>a[i];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
cin>>w[i][j];
}
dfs(1,0,0,0);
cout<<ans<<endl;
return 0;
}
算法2
(dp)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
int n,k,m,ans;
int w[N][N];
int a[N];
int dp[N][N], last[N][N];
int main(){
cin >> n >> k >> m;
for(int i = 1; i <= m; i++) cin>>a[i];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin>>w[i][j];
}
}
for(int i = 1; i <= m; i++){
int lim = min(i-1,k);
for(int j = 0; j <= lim; j++){ //根据dp定义,i是不能删除的;
int sum = 0;
for(int l = 0; l <= j; l++){ //从dp[i-k-1][j-k] 迭代到 dp[i-1][j]
int pre = i-l-1, cur = j-l;
int cur_sum = dp[pre][cur] + w[a[pre]][a[i]];
if(cur_sum > sum){
sum = cur_sum;
last[i][j] = pre;
}
}
dp[i][j] = sum;
ans = max(ans,dp[i][j]);
}
}
cout<<ans<<endl;
return 0;
}