洛谷P1541乌龟棋

bad_404 · 2018-06-03 21:58:56 · 个人记录

动归，四位数组存每一张牌的最优解，num数组用来存棋盘，上代码。

#include<bits/stdc++.h>
using namespace std;
int n,m,num[400],f[42][42][42][42],r,g[5];
int main()
{
    int i,j,k,l,t,a,b;
    scanf("%d%d",&n,&m);
    for(a=1;a<=n;a++)
    scanf("%d",&num[a]);
    for(b=1;b<=m;b++)
    {
        scanf("%d",&t);
        g[t]++;
    }
    f[0][0][0][0]=num[1];
    for(i=0;i<=g[1];i++)
       for(j=0;j<=g[2];j++)
          for(k=0;k<=g[3];k++)
             for(l=0;l<=g[4];l++)
             {
                r=1+i+j*2+k*3+l*4;//以下四句分别表示最后使用的那张牌之前的最优解，类似于背包问题
                if(i!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+num[r]);
                if(j!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+num[r]);
                if(k!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+num[r]);
                if(l!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+num[r]);
             }
    printf("%d",f[g[1]][g[2]][g[3]][g[4]]);
    return 0;
}