AcWing 3499. 序列最大收益
原题链接
中等
作者:
英特耐雄纳尔
,
2021-05-18 17:03:31
,
所有人可见
,
阅读 238
// DP 最长上升子序列的扩展
// 可以发现 第一个和最后一个是一定会选的,因为这会增加收益
// f[][]表示在前i个数中选,而且第i个选中,删除掉j个的最大收益
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n,k,m;
int arr[N],w[N][N];
int f[N][N];
int main()
{
cin>>n>>k>>m;
for(int i=1;i<=m;i++) scanf("%d", &arr[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;
for(int i=2;i<=m;i++)
{
for(int j=0;j<=k;j++) //最多删除k个
{
for(int u=1;u<i;u++) //枚举状态转移
{
if(j>=i-u-1)
{
f[i][j]=max(f[i][j],f[u][j-(i-u-1)]+w[arr[u]][arr[i]]);
}
}
}
}
int res=0;
for(int i=0;i<=k;i++) res=max(res,f[m][i]);
cout<<res;
}
//f[][]表示在前i个元素中删,并且第i个不删,删j个的最大权值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n,k,m;
int w[N][N];
int arr[N];
int f[N][N];
int main()
{
cin>>n>>k>>m;
for(int i=1;i<=m;i++) cin>>arr[i];
for (int i = 1; i <= n; i ++ )
{
for(int j=1;j<=n;j++) cin>>w[i][j];
}
memset(f,-0x3f,sizeof f);
f[1][0]=0;
for(int i=1;i<=m;i++) //从第1个数开始循环
{
for(int j=0;j<=k;j++)
{
for(int u=1;u<i;u++)
{
if(i-u-1<=j)
{
f[i][j]=max(f[i][j],f[u][j-(i-u-1)]+w[arr[u]][arr[i]]); //f[][]的定义
}
}
}
}
int res=0;
for(int i=0;i<=k;i++) res=max(res,f[m][i]);
cout<<res;
}