把每个牌选多少个塞进dp的四个维度里,就可以做到无后效性了
#include<bits/stdc++.h>
using namespace std;
#define for1(i,a,b) for(ll i = a;i <=b;i++)
#define ll long long
ll n,a[50000],p[10],x,m,dp[50][50][50][50];
int main()
{
int x,y,k,ji;
scanf("%d%d",&n,&m);
for1(i,1,n)scanf("%d",&a[i]);
for1(i,1,m) scanf("%d",&x),p[x]++;
dp[0][0][0][0]=a[1];
for1(i1,0,p[1])
{
for1(i2,0,p[2])
{
for1(i3,0,p[3])
{
for1(i4,0,p[4])
{
int ji=i1+i2*2+i3*3+i4*4+1;
if(i1!=0) dp[i1][i2][i3][i4]=max(dp[i1][i2][i3][i4],dp[i1-1][i2][i3][i4]+a[ji]);
if(i2!=0) dp[i1][i2][i3][i4]=max(dp[i1][i2][i3][i4],dp[i1][i2-1][i3][i4]+a[ji]);
if(i3!=0) dp[i1][i2][i3][i4]=max(dp[i1][i2][i3][i4],dp[i1][i2][i3-1][i4]+a[ji]);
if(i4!=0) dp[i1][i2][i3][i4]=max(dp[i1][i2][i3][i4],dp[i1][i2][i3][i4-1]+a[ji]);
}
}
}
}
printf("%d",dp[p[1]][p[2]][p[3]][p[4]]);
return 0;
}
标签:20,P1541,dp1,NOIP2010,2022,乌龟
From: https://www.cnblogs.com/yyx525jia/p/16711178.html