P1541 乌龟棋


四维DP——四种状态，所以四维DP

f [ i ] [ j ] [ k ] [ l ] f[i][j][k][l] f[i][j][k][l]:表示牌号分别为1,2,3,4，的时候用了i,j,k,l张牌
思路详解

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const ll N=40;
ll n,m,f[N][N][N][N],arr[1000],b[100];
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld",&arr[i]);
    ll tmp;
    for(int i=1;i<=m;++i)
        scanf("%lld",&tmp),b[tmp]++;
    f[0][0][0][0]=arr[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)
                {
                    ll p=1+i+j*2+k*3+l*4;
                    if(i)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+arr[p]);
                    if(j)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+arr[p]);
                    if(k)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+arr[p]);
                    if(l)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+arr[p]);
                }
    printf("%lld\n",f[b[1]][b[2]][b[3]][b[4]]);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜