AcWing 3499. 序列最大收益
原题链接
中等
作者:
TYUTICPC05
,
2021-05-16 12:29:29
,
所有人可见
,
阅读 261
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int dp[210][210];
int a[210];
int v[210][210];
int main()
{
int n,k,m;
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",&v[i][j]);
for(int i=2;i<=m;i++) //前i个点;
for(int j=0;j<i&&j<=k;j++) //删(0~i-1)个点;
for(int u=0;u<=j;u++) //i左边删了个点 ;
dp[i][j]=max(dp[i-u-1][j-u]+v[a[i]][a[i-u-1]],dp[i][j]); // i左边删了u个点 前一个点是i-u-1;还要删j-u个点;
int ans=0;
for(int i=0;i<=k;i++)
ans=max(dp[m][i],ans); //枚举
cout<<ans<<endl;
return 0;
}