NOIP 2011 乌龟棋 解题报告

从数据规模可以看出本题用暴力搜索是行不通的，考虑使用动态规划。我折腾了一个多小时，竟然没有想出一个合适的状态表示。最后无奈地看了题解，程序很简单。

f[a][b][c][d]表示使用a个前进1的卡片，b个前进2的卡片……可以获得的最大分值

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03
04 int count[5];   //记录每种卡片出现次数
05 int value[360];  //每个位置的分值
06 int M,N;
07
08 long f[41][41][41][41];
09
10 long get_max(long a,long b)
11 {
12     if(a > b)   return a;
13     return b;
14 }
15
16 void solve()
17 {
18     int i,j,k,t;
19     int pos;
20     f[0][0][0][0] = value[0];
21     for(i = 0;i <= count[1];i ++)
22         for(j = 0;j <= count[2];j ++)
23             for(k = 0;k <= count[3];k ++)
24                 for(t = 0;t <= count[4];t ++)
25                 {
26                     pos = i + 2 * j + 3 * k + 4 * t;  //乌龟的位置
27                     f[i][j][k][t + 1] = get_max(f[i][j][k][t + 1],f[i][j][k][t] + value[pos + 4]);
28                     f[i][j][k + 1][t] = get_max(f[i][j][k + 1][t],f[i][j][k][t] + value[pos + 3]);
29                     f[i][j + 1][k][t] = get_max(f[i][j + 1][k][t],f[i][j][k][t] + value[pos + 2]);
30                     f[i + 1][j][k][t] = get_max(f[i + 1][j][k][t],f[i][j][k][t] + value[pos + 1]);
31                 }
32 }
33
34 int main()
35 {
36     scanf("%d%d",&N,&M);
37     int i,step;
38     for(i = 0;i < N;i ++)
39         scanf("%d",&value[i]);
40     for(i = 0;i < M;i ++)
41     {
42         scanf("%d",&step);
43         count[step] ++;
44     }
45     solve();
46     printf("%ld\n",f[count[1]][count[2]][count[3]][count[4]]);
47     return 0;
48 }

虽然简单，不过这种状态表示方法依然值得分析。

可行吗？
对于一个给定的棋盘和卡片，由于卡片全部都要使用，所以可以获得的最大分值一定是唯一的。那么，获得最大分值的方案也是可以确定的（虽然说方案可能有多解情况），所以这种状态表示是唯一的。
假如我们知道某一时刻使用过的每一种卡片的数量，那么当前乌龟在棋盘上的位置就是确定的，然后我们对剩下的卡片进行选择，分别计算出使用某个卡片后的可以达到的最大分值。

题目条件的暗示
题目中有说明卡片只有4种，并且要全部使用（我最初一直不知道这个条件拿来干什么的），每个卡片的数量不超过40.通过题目条件的暗示，也容易想到这种解法。

类似的题目
交换游戏，参见http://tenpages.blogcn.com/archives/72