洛谷 P1541 乌龟棋

题目传送门

解题思路:

一开始脑抽,以为是一道背包,结果写完后发现并不是一道背包.....

f[i][j][x][y]表示1,2,3,4种牌各用了i,j,x,y张可以获得的最大值.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #define f(i,j,x,y) f[i][j][x][y]
 4
 5 using namespace std;
 6
 7 int n,m,a[351],sum[5],f[41][41][41][41];
 8
 9 int main() {
10     scanf("%d%d",&n,&m);
11     for(int i = 1;i <= n; i++)
12         scanf("%d",&a[i]);
13     f(0,0,0,0) = a[1];
14     for(int i = 1;i <= m; i++) {
15         int u;
16         scanf("%d",&u);
17         sum[u]++;
18     }
19     for(int i = 0;i <= sum[1]; i++)
20         for(int j = 0;j <= sum[2]; j++)
21             for(int x = 0;x <= sum[3]; x++)
22                 for(int y = 0;y <= sum[4]; y++) {
23                     int now = 1 * i + 2 * j + 3 * x + 4 * y + 1;
24                     if(i != 0) f(i,j,x,y) = max(f(i,j,x,y),f(i-1,j,x,y) + a[now]);
25                     if(j != 0) f(i,j,x,y) = max(f(i,j,x,y),f(i,j-1,x,y) + a[now]);
26                     if(x != 0) f(i,j,x,y) = max(f(i,j,x,y),f(i,j,x-1,y) + a[now]);
27                     if(y != 0) f(i,j,x,y) = max(f(i,j,x,y),f(i,j,x,y-1) + a[now]);
28                 }
29     printf("%d",f(sum[1],sum[2],sum[3],sum[4]));
30     return 0;
31 }

//NOIP提高2010 T2