[洛谷 1541][NOIP2010]乌龟棋

题目链接

https://www.luogu.org/problem/P1541

题解

可以用 \(f(i,j,k,l)\)来表示用了 \(i\) 张 \(1\) 牌，\(j\) 张 \(2\) 牌，\(k\) 张 \(3\) 牌，\(l\) 张 \(4\) 牌时，能够得到的最多分数。

注意判断一下状态转移的合法性即可。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[350],f[45][45][45][45],t[5];
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 for(int i=1;i<=m;i++)
 {
  int b;
  scanf("%d",&b);
  t[b]++;
 }
 f[0][0][0][0]=a[1];//不使用牌时，自动获得起点的分数
 for(int i=0;i<=t[1];i++)
  for(int j=0;j<=t[2];j++)
   for(int k=0;k<=t[3];k++)
    for(int l=0;l<=t[4];l++)
    {
     int num=i+2*j+3*k+4*l+1;
     if(i)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[num]);//使用1牌
     if(j)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[num]);//使用2牌
     if(k)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[num]);//使用3牌
     if(l)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[num]);//使用4牌
    }
 printf("%d\n",f[t[1]][t[2]][t[3]][t[4]]);
 return 0;
}