三维dp

#include<cstdio>
#define max(a,b) a>b?a:b
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int f[41][41][41],a[351],n,m,g[4],t;
int main()
{
    scanf("%d%d",&n,&m);
    r(i,1,n) scanf("%d",&a[i]);
    while(m--) {scanf("%d",&t);g[t-1]++;}
    f[0][0][0]=0;
    r(i,0,g[0])
    r(j,0,g[1])
    r(k,0,g[2])
    r(l,0,g[3])
    {
        t=a[1+i+(j<<1)+k*3+(l<<2)];
        if(j) f[j][k][l]=max(f[j][k][l],f[j-1][k][l]);
        if(k) f[j][k][l]=max(f[j][k][l],f[j][k-1][l]);
        if(l) f[j][k][l]=max(f[j][k][l],f[j][k][l-1]);
        f[j][k][l]+=t;
    }
    printf("%d",f[g[1]][g[2]][g[3]]);
}

DP基础题：
由于题目告诉我们确保用完牌恰好能走完，题目被大大简化
我们用数组dp[a][b][c][d]表示用了a张一步牌，b张2步牌，c张3步牌，d张4布牌所能得到的最高分
num[i-1]表示i步牌的张数；path[]数组记录路径信息；card[]数组记录卡牌信息。
则有dp[0][0][0][0]=path[0]//什么牌都不用就可以获得起点的分数
并且有**path[a+2b+3c+4d]为当前点的分数**
之后四重循环，分别枚举a,b,c,d;
对于枚举的每种情况:
dp[a][b][c][d]=max(dp[a][b][c][d],**之前的一步操作**+**[a+2b+3c+4d]**)
这句话的意思是：**是不进行前一步操作比较赚还是进行比较赚**
为什么要判断a,b,c,d是否大于0呢？**都没牌了哪里还存在前一步操作呢？**
ok!最后答案被保存在dp[num[0]][[num[1]][num[2]][num[3]]里，输出即可。
talk is cheap shou me the code:
#include<iostream>
using namespace std;
int N,M,pv,num[4],path[500],card[500],dp[42][42][42][42];
int main()
{
cin>>N>>M;
for(int i=0;i<N;i++)cin>>path[i];
for(int i=0;i<M;i++){cin>>card[i];num[card[i]-1]+=1;}
dp[0][0][0][0]=path[0];
for(int a=0;a<=num[0];a++)
for(int b=0;b<=num[1];b++)
for(int c=0;c<=num[2];c++)
for(int d=0;d<=num[3];d++)
{pv=a+b*2+c*3+d*4;
if(a>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a-1][b][c][d]+path[pv]);
if(b>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b-1][c][d]+path[pv]);
if(c>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c-1][d]+path[pv]);
if(d>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c][d-1]+path[pv]);}
cout<<dp[num[0]][num[1]][num[2]][num[3]];
return 0;
}

simple dp
f[i][j][k][l]表示用了i张前进1的卡片,j张前进2的卡片,k张前进3的卡片和l张前进d的卡片。dp的时候直接枚举每一个。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m;
int a[400],b[400],cnt[5];
int f[45][45][45][45];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i],cnt[b[i]]++;
    for(int a1=0;a1<=cnt[1];a1++)
        for(int a2=0;a2<=cnt[2];a2++)
            for(int a3=0;a3<=cnt[3];a3++)
                for(int a4=0;a4<=cnt[4];a4++)
                {
                    if(a1)
                        f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1-1][a2][a3][a4]);
                    if(a2)
                        f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1][a2-1][a3][a4]);
                    if(a3)
                        f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1][a2][a3-1][a4]);
                    if(a4)
                        f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1][a2][a3][a4-1]);
                    f[a1][a2][a3][a4]+=a[a1+2*a2+3*a3+4*a4+1];
                }
    printf("%d\n",f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
    return 0;
}

简单的DP

#include<bits/stdc++.h>
using namespace std;
int a[400];
int f[41][41][41][41];
int main()
{
    int n,m,x,s1=0,s2=0,s3=0,s4=0,s;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        if(x==1)
        {
            s1++;
        }
        else if(x==2)
        {
            s2++;
        }
        else if(x==3)
        {
            s3++;
        }
        else
        {
            s4++;
        }
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=s1;i++)
    {
        for(int j=0;j<=s2;j++)
        {
            for(int k=0;k<=s3;k++)
            {
                for(int h=0;h<=s4;h++)
                {
                    s=0;
                    if(i!=0)
                    {
                        s=max(s,f[i-1][j][k][h]);
                    }
                    if(j!=0)
                    {
                        s=max(s,f[i][j-1][k][h]);
                    }
                    if(k!=0)
                    {
                        s=max(s,f[i][j][k-1][h]);
                    }
                    if(h!=0)
                    {
                        s=max(s,f[i][j][k][h-1]);
                    }
                    f[i][j][k][h]=s+a[i+2*j+3*k+4*h+1];
                }
            }
        }
    }
    printf("%d",f[s1][s2][s3][s4]);
    return 0;
}

DP

#include<cstdio>
#include<algorithm>

using namespace std;

const int MAXN = 355;
const int MAXM = 125;
int n, m, a[MAXN], b[MAXM], am[5];
int dp[41][41][41][41];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &b[i]), am[b[i]]++;
    dp[0][0][0][0] = a[1];
    for(int i = 0; i <= am[1]; i++){
        for(int j = 0; j <= am[2]; j++){
            for(int k = 0; k <= am[3]; k++){
                for(int l = 0; l <= am[4]; l++){
                    int t = i+2*j+3*k+4*l+1;
                    if(i>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l]+a[t]);
                    if(j>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l]+a[t]);
                    if(k>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k-1][l]+a[t]);
                    if(l>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l-1]+a[t]);
                }
            }
        }
    }
    printf("%d", dp[am[1]][am[2]][am[3]][am[4]]);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;++i)
int f[41][41][41][41], a[350], t, num[5];
int n,m;
inline int max(int x,int y) {return x>y?x:y;}
int main(){
        scanf("%d%d",&n,&m);
        memset(f,0,sizeof f);
        memset(num,0,sizeof num);
        rep(i,1,n) scanf("%d",&a[i]);
        rep(i,1,m) scanf("%d",&t), ++num[t];
        rep(i,0,num[1]) rep(j,0,num[2]) rep(k,0,num[3]) rep(l,0,num[4]){
                int temp = 0;
                if (i) temp = max(temp, f[i-1][j][k][l]);
                if (j) temp = max(temp, f[i][j-1][k][l]);
                if (k) temp = max(temp, f[i][j][k-1][l]);
                if (l) temp = max(temp, f[i][j][k][l-1]);
                f[i][j][k][l] = temp + a[i*1+j*2+k*3+l*4+1];
        }
        cout << f[num[1]][num[2]][num[3]][num[4]] << endl;
        return 0;
}

有2000年代风格的题目
f[i][j][k][l]表示各型号的卡用了几次
随便dp

注意有个坑：
棋子是从1开始跳的，而不是从0开始

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 350 + 5;
const int maxm = 120 + 5;
const int maxtype = 40 + 5;

int n, m;
int score[maxn];
int card[5];
int d[maxtype][maxtype][maxtype][maxtype];

int dp (int coordi, int c1, int c2, int c3, int c4) {
    int& ans = d[c1][c2][c3][c4];
    if (ans >= 0) return ans;
    
    ans = 0;
    int v = score[coordi];
    if (c1) ans = max(ans, dp(coordi+1, c1-1, c2, c3, c4)+v);
    if (c2) ans = max(ans, dp(coordi+2, c1, c2-1, c3, c4)+v);
    if (c3) ans = max(ans, dp(coordi+3, c1, c2, c3-1, c4)+v);
    if (c4) ans = max(ans, dp(coordi+4, c1, c2, c3, c4-1)+v);
    
    return ans;
}

int main ()
{
//  freopen("in.txt", "r", stdin);
    memset(d, -1, sizeof(d));
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> score[i];
    for (int i = 0; i < m; i++) {
        int tmp; cin >> tmp;
        card[tmp]++;
    }
    
    d[0][0][0][0] = score[n-1];
    cout << dp(0, card[1], card[2], card[3], card[4]);
    return 0;
}

位置是可以用爬行卡算来的！！！
这一道水题居然花了一个小时、、不可思议
``` c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int N[400], M[200], n, m;
int num[5];
int dp[41][41][41][41];

inline int pos(int a, int b, int c, int d) {
return 1+a+(b)*2+(c)*3+(d)*4;
}

int main()
{
memset(dp, 0, sizeof dp);
memset(num, 0,sizeof num);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &N[i]);
for (int i = 1; i <= m; i++) {
scanf("%d", &M[i]);
num[M[i]]++;
}
for (int i = 0; i <= num[1]; i++)
for (int j = 0; j <= num[2]; j++)
for (int k = 0; k <= num[3]; k++)
for (int l = 0; l <= num[4]; l++) {
int p = pos(i,j,k,l);
if (i != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l]+N[p]);
if (j != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l]+N[p]);
if (k != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k-1][l]+N[p]);
if (l != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l-1]+N[p]);
}
cout << dp[num[1]][num[2]][num[3]][num[4]]+N[1] << endl;
return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
int f[41][41][41][41],a[401],b[5],n,m;
int max(int x,int y)
{
if (x>y) return x;
else return y;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=m;i++)
{
int k;
cin>>k;
b[k]++;
}

memset(f,0,sizeof(f));
f[0][0][0][0]=a[1];
for (int i=0;i<=b[1];i++)
{
for (int j=0;j<=b[2];j++)
{
for (int k=0;k<=b[3];k++)
{
for (int l=0;l<=b[4];l++)
{
if (i>0) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[1+i*1+j*2+k*3+l*4]);
if (j>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[1+i*1+j*2+k*3+l*4]);
if (k>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[1+i*1+j*2+k*3+l*4]);
if (l>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[1+i*1+j*2+k*3+l*4]);
}
}
}
}
cout<<f[b[1]][b[2]][b[3]][b[4]];
}
AC40 纪念一下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[350],b[120],n,m,dpp[40][40][40][40];
int ka1=0,ka2=0,ka3=0,ka4=0;
inline int max(int l,int o)
{
if(l>o)
return l;
return o;
}
int dp(int aa)
{
int count2,k1=0;
if(dpp[ka1][ka2][ka3][ka4]!=-1)
return dpp[ka1][ka2][ka3][ka4];
if(ka1)
{
ka1--;
k1=dp(aa+1)+a[aa+1];
ka1++;
}
if(ka2)
{
ka2--;
k1=max(k1,dp(aa+2)+a[aa+2]);
ka2++;
}
if(ka3)
{
ka3--;
k1=max(k1,dp(aa+3)+a[aa+3]);
ka3++;
}
if(ka4)
{
ka4--;
k1=max(k1,dp(aa+4)+a[aa+4]);
ka4++;
}
dpp[ka1][ka2][ka3][ka4]=k1;
return k1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
memset(dpp,-1,sizeof(dpp));
for(int i=0;i<m;i++)
{
scanf("%d",&b[i]);
if(b[i]==1)
ka1++;
else if(b[i]==2)
ka2++;
else if(b[i]==3)
ka3++;
else
ka4++;
}
int k=dp(0)+a[0];
cout<<k;
return 0;
}
淡定dp+优化

四个状态i1,i2,i3,i4代表用的爬行卡数量
转移方程
f[i1,i2,i3,i4]:=max(f[i1,i2,i3,i4],
f[i1-1,i2,i3,i4],f[i1,i2-1,i3,i4],
f[i1,i2,i3-1,i4],f[i1,i2,i3,i4-1])+
a[i1+2*i2+3*i3+4*i4+1];

/*

Author : Slience_K
Belong : C++
Pro : NOIP 2010 - 2

*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n , x , m , a[ 5 ] , d[ 355 ] , f[ 45 ][ 45 ][ 45 ][ 45 ];
int main(){
scanf( "%d%d" , &n , &m );
for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &d[ i ] );
for( int i = 1 ; i <= m ; i++ ){
scanf( "%d" , &x );
a[ x ]++;
}
int dis , maxn;
f[ 0 ][ 0 ][ 0 ][ 0 ] = d[ 1 ];
for( int i = 0 ; i <= a[ 1 ] ; i++ )
for( int j = 0 ; j <= a[ 2 ] ; j++ )
for( int k = 0 ; k <= a[ 3 ] ; k++ )
for( int l = 0 ; l <= a[ 4 ] ; l++ )
if (( i == 0 )&&( j == 0 )&&( k == 0 )&&( l == 0 )) continue;
else{
maxn = 0;
if (( a[ 1 ] )&&( i >= 1 ))
maxn = max( maxn , f[ i - 1 ][ j ][ k ][ l ] );
if (( a[ 2 ] )&&( j >= 1 ))
maxn = max( maxn , f[ i ][ j - 1 ][ k ][ l ] );
if (( a[ 3 ] )&&( k >= 1 ))
maxn = max( maxn , f[ i ][ j ][ k - 1 ][ l ] );
if (( a[ 4 ] )&&( l >= 1 ))
maxn = max( maxn , f[ i ][ j ][ k ][ l - 1 ] );
dis = i + 2 * j + 3 * k + 4 * l + 1;
maxn += d[ dis ];
f[ i ][ j ][ k ][ l ] = maxn;
}
printf( "%d" , f[ a[ 1 ] ][ a[ 2 ] ][ a[ 3 ] ][ a[ 4 ] ] );
return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
long n,m,i,j,k,l,tmp,score[351]={0},card[5]={0},f[41][41][41][41]={0};
int main(){
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;++i)scanf("%ld",&score[i]);
for(i=1;i<=m;++i){
scanf("%ld",&tmp);
++card[tmp];
}
for(i=0;i<=card[1];++i)
for(j=0;j<=card[2];++j)
for(k=0;k<=card[3];++k)
for(l=0;l<=card[4];++l){
long tmp1=0,tmp2=0,tmp3=0,tmp4=0;
if(i)tmp1=f[i-1][j][k][l];
if(j)tmp2=f[i][j-1][k][l];
if(k)tmp3=f[i][j][k-1][l];
if(l)tmp4=f[i][j][k][l-1];
f[i][j][k][l]=max(max(tmp1,tmp2),max(tmp3,tmp4))+score[i*1+j*2+k*3+l*4+1];
}
printf("%ld",f[card[1]][card[2]][card[3]][card[4]]);
}

f[i][j][s][t]=max(f[i-1][j][k][t],f[i][j-1][k][t],f[i][j][k-1][t],f[i][j][k][t-1])+ge[i+j+j+k+k+k+t+t+t+t+1]
四维动归。。。
f[i][j][s][t]移动i个一步，j个两步，s个三步，t个四步的最小值
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ge[500],ka[500],f[45][45][45][45],num1,num2,num3,num4;
int main()
{
freopen("tortoise.in","r",stdin);
freopen("tortoise.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&ge[i]);
for(int i=1;i<=m;i++){
scanf("%d",&ka[i]);
if(ka[i]==1) num1++;
if(ka[i]==2) num2++;
if(ka[i]==3) num3++;
if(ka[i]==4) num4++;
}
f[0][0][0][0]=ge[1];
for(int i=0;i<=num1;i++)
for(int j=0;j<=num2;j++)
for(int k=0;k<=num3;k++)
for(int t=0;t<=num4;t++){
if(i>0) f[i][j][k][t]=max(f[i-1][j][k][t],f[i][j][k][t]);
if(j>0) f[i][j][k][t]=max(f[i][j-1][k][t],f[i][j][k][t]);
if(k>0) f[i][j][k][t]=max(f[i][j][k-1][t],f[i][j][k][t]);
if(t>0) f[i][j][k][t]=max(f[i][j][k][t-1],f[i][j][k][t]);
if(i>0||j>0||k>0||t>0) f[i][j][k][t]+=ge[i+j*2+k*3+t*4+1];
}
printf("%d",f[num1][num2][num3][num4]);
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 350+10;

int a[MAXN], f[41][41][41][41], num[MAXN];

int main()
{
int n, m, b;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
scanf("%d", &a[i]);
for(int i=1; i<=m; i++){
scanf("%d", &b);
num[b]++;
}
f[0][0][0][0] = a[1];
for(int i=0; i<=num[1]; i++)
for(int j=0; j<=num[2]; j++)
for(int k=0; k<=num[3]; k++)
for(int l=0; l<=num[4]; l++){
int bri = i + j*2 + k*3 + l*4 + 1;
if(i>0) f[i][j][k][l] = max(f[i][j][k][l], f[i-1][j][k][l]+a[bri]);
if(j>0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j-1][k][l]+a[bri]);
if(k>0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k-1][l]+a[bri]);
if(l>0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l-1]+a[bri]);
}
printf("%d", f[num[1]][num[2]][num[3]][num[4]]);
return 0;
}
四维DP

P1775乌龟棋
Accepted

记录信息

评测状态 Accepted
题目 P1775 乌龟棋
递交时间 2015-07-07 18:48:55
代码语言 C++
评测机 VijosEx
消耗时间 387 ms
消耗内存 12460 KiB
评测时间 2015-07-07 18:48:58

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 12460 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 12456 KiB, score = 10

测试数据 #2: Accepted, time = 31 ms, mem = 12460 KiB, score = 10

测试数据 #3: Accepted, time = 31 ms, mem = 12460 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 12456 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 12456 KiB, score = 10

测试数据 #6: Accepted, time = 46 ms, mem = 12460 KiB, score = 10

测试数据 #7: Accepted, time = 62 ms, mem = 12456 KiB, score = 10

测试数据 #8: Accepted, time = 78 ms, mem = 12460 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 12460 KiB, score = 10

Accepted, time = 387 ms, mem = 12460 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

int n , m;
int i , j , k , l;
int a , b , c , d , e;
int t[350 + 10];
int f[40 + 2][40 + 2][40 + 2][40 + 2];

int dp( int x , int y , int z , int w )
{
if( f[x][y][z][w] != -1 )
return f[x][y][z][w];
if( !x && !y && !z && !w )
return 0;
int pos = ( a - x ) * 1 + ( b - y ) * 2 + ( c - z ) * 3 + ( d - w ) * 4 + 1;
int maxd = 0;
if( x > 0 )
maxd = max( maxd , dp( x - 1 , y , z , w ) + t[ pos + 1 ] );
if( y > 0 )
maxd = max( maxd , dp( x , y - 1 , z , w ) + t[ pos + 2 ] );
if( z > 0 )
maxd = max( maxd , dp( x , y , z - 1 , w ) + t[ pos + 3 ] );
if( w > 0 )
maxd = max( maxd , dp( x , y , z , w - 1 ) + t[ pos + 4 ] );
f[x][y][z][w] = maxd;
return f[x][y][z][w];
}

int main()
{
for( i = 0 ; i <= 40 ; i++ )
for( j = 0 ; j <= 40 ; j++ )
for( k = 0 ; k <= 40 ; k++ )
for( l = 0 ; l <= 40 ; l++ )
f[i][j][k][l] = -1;
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
scanf( "%d" , &t[i] );
for( j = 1 ; j <= m ; j++ )
{
scanf( "%d" , &e );
if( e == 1 )
a++;
if( e == 2 )
b++;
if( e == 3 )
c++;
if( e == 4 )
d++;
}
cout << dp( a , b , c , d ) + t[1] << endl;
return 0;
}

#include <iostream>
using namespace std;
const int INF=100000000;
int f[350+5];
int d[350+5][45][45][45];
bool vis[350+5][45][45][45];
int dp(int,int,int,int,int);
int K1,K2,K3,K4;
int N,M;
int main()
{
ios::sync_with_stdio(false);
cin>>N>>M;
for(int i=1;i<=N;++i)
cin>>f[i];
for(int i=1;i<=M;++i)
{
int t=0;
cin>>t;
if(t==1) K1++;
if(t==2) K2++;
if(t==3) K3++;
if(t==4) K4++;
}
cout<<dp(N,K1,K2,K3,M-K1-K2-K3)<<endl;

}
int dp(int n,int k1,int k2,int k3,int k4)
{
if(vis[n][k1][k2][k3]==1) return d[n][k1][k2][k3];
if(k1<0||k2<0||k3<0||k4<0) return -INF;
if(n==1) return f[1];
if(n<1) return -INF;
vis[n][k1][k2][k3]=1;
if(dp(n-1,k1-1,k2,k3,k4)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-1,k1-1,k2,k3,k4)+f[n];
if(dp(n-2,k1,k2-1,k3,k4)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-2,k1,k2-1,k3,k4)+f[n];
if(dp(n-3,k1,k2,k3-1,k4)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-3,k1,k2,k3-1,k4)+f[n];
if(dp(n-4,k1,k2,k3,k4-1)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-4,k1,k2,k3,k4-1)+f[n];
return d[n][k1][k2][k3];
}

见过最水的DP，我这种蒟蒻居然能自己写出状态转移方程~~
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#define FOR(a,b) for(int i=a;i<=b;i++)
using namespace std;
int N,M,tmp;
int d[41][41][41][41];
int a[5];
int b[351];
int main()
{
ios::sync_with_stdio(false);
cin>>N>>M;
FOR(0,N-1) cin>>b[i];
FOR(1,M)
{
cin>>tmp;
a[tmp]++;
}
d[0][0][0][0]=b[0];
for(int i=0;i<=a[1];i++)
for(int j=0;j<=a[2];j++)
for(int k=0;k<=a[3];k++)
for(int l=0;l<=a[4];l++)
{
tmp=i+2*j+3*k+4*l;
if(i) d[i][j][k][l]=max(d[i][j][k][l],d[i-1][j][k][l]+b[tmp]);
if(j) d[i][j][k][l]=max(d[i][j][k][l],d[i][j-1][k][l]+b[tmp]);
if(k) d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k-1][l]+b[tmp]);
if(l) d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k][l-1]+b[tmp]);
}
cout<<d[a[1]][a[2]][a[3]][a[4]]<<endl;
return 0;
}

记忆化搜索可以排除冗余的状态

#include<iostream>
#include<fstream>
#include<cstring>

using namespace std;

inline int update(int &a,int b)
{
a=a>b?a:b;
}

int N,M,map[351],count[5],f[41][41][41][41],ans=0;

int main()
{
ifstream cin("tortoise.in");
ofstream cout("tortoise.out");
memset(f,0,sizeof(f));
memset(count,0,sizeof(count));
cin>>N>>M;
for(int i=1;i<=N;i++)
cin>>map[i];
for(int i=1,card;i<=M;i++)
{
cin>>card;
count[card]++;
}
f[0][0][0][0]=map[1];
for(int i=0,now;i<=count[1];i++)
{
now=1+i;
if (now>N) break;
for(int j=0;j<=count[2];j++)
{
now=1+i+(j<<1);
if (now>N) break;
for(int k=0;k<=count[3];k++)
{
now=1+i+(j<<1)+k*3;
if (now>N) break;
for(int l=0;l<=count[4];l++)
{
int now=1+i+(j<<1)+k*3+(l<<2);
if (now>N) break;
if (i>0) update(f[i][j][k][l],f[i-1][j][k][l]+map[now]);
if (j>0) update(f[i][j][k][l],f[i][j-1][k][l]+map[now]);
if (k>0) update(f[i][j][k][l],f[i][j][k-1][l]+map[now]);
if (l>0) update(f[i][j][k][l],f[i][j][k][l-1]+map[now]);
if (now==N) ans=max(ans,f[i][j][k][l]);
}
}
}
}
cout<<ans<<endl;
return 0;
}