YSDPFXF
dp[i][j] 只考虑前i个数,共删除了j个数 且保留了第i个数的所有方案的集合 最大值
- 数列的首位,应该保留 删除会降低最大收益
- 删除的是0-k个 是一个区间,所以上一个状态是“u”,应该枚举出这个u
- i-u-1是数列删除的数量 例如4-2-1 = 1,保留了最后一个4,上一个末尾状态是2,删除的是3(一个)
将dp数组初始化负无穷
只需要预处理第一个数字即可
for() // 枚举到第几个位置
for() // 枚举删除数量
for() // 枚举前一个位置U
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n,k,m;
int a[N] , w[N][N];
int f[N][N]; // 从前i个中删除j个的最大值,且保留了i 删除的是i前面的
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i = 1; i <= m; i ++ )scanf("%d",&a[i]);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
scanf("%d",&w[i][j]);
memset(f , -0x3f , sizeof f);
f[1][0] = 0; // 只需要给第一个数初始化,目前只有一个数字 没删除 收益为0
for(int i = 2; i <= m; i ++ ) //
for(int j = 0; j <= k ; j ++ ) // 删除的数量
for(int u = 1; u < i; u ++ ) // 枚举 删除之后 留下的 i 前面的位置u
if(j >= i-u-1)
f[i][j] = max(f[i][j] , f[u][j - (i - u - 1)] + w[a[u]][a[i]]);
int res = 0;
for(int j = 0; j <= k; j ++ )
res = max(res , f[m][j]);
printf("%d\n",res);
return 0;
}