AcWing 312. 乌龟棋
原题链接
简单
作者:
Feelme
,
2023-03-23 19:44:06
,
所有人可见
,
阅读 120
#include<bits/stdc++.h>
using namespace std;
const int N = 500;
int n,m;
int s[N],card[N];
int dp[40][40][40][40]; //dp 表示各种牌的选择张数的最大值 状态方程按最后一张牌的不同划分
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
for(int i=0;i<m;i++)
{
int x;
cin >> x;
card[x]++;
}
for(int i=0;i<=card[1];i++)
{
for(int j=0;j<=card[2];j++)
{
for(int k=0;k<=card[3];k++)
{
for(int t=0;t<=card[4];t++)
{
int x=s[i+2*j+3*k+4*t];
int &y=dp[i][j][k][t];
y=t;
if(i) y=max(y,dp[i-1][j][k][t]+x);
if(j) y=max(y,dp[i][j-1][k][t]+x);
if(k) y=max(y,dp[i][j][k-1][t]+x);
if(t) y=max(y,dp[i][j][k][t-1]+x);
}
}
}
}
cout<<dp[card[1]][card[2]][card[3]][card[4]]+s[0];
return 0;
}