Noip2010 第2题 tortoise 乌龟棋 【题意分析】
乌龟从1号格子出发，爬行至第n号格子，它可以连续走1步、2步、3步、4步。当它停留在第i号格子时，可以获得奖励才c[i]，已知一共要走a1个1步、a2个2步、a3个3步、a4个4步，问怎样安排顺序使得获得的奖励最多 【输入】
9 5 第1行 两个整数n、m，分别为地图长度及卡片个数 6 10 14 2 8 8 18 5 17 第2行 n个整数，表示每个格子的奖励数 1 3 1 2 1 第3行 m个整数，表示m张卡片上的数字 【输出】
73 获得的最大奖励数 【样例分析】
小明使用爬行卡片顺序为 1，1，3，1，2，得到的分数为 6+10+14+8+18+17=73。 【分析】
很显然这是一个动态规划题目，对于每一个停留位置所能获得的累积奖励，只与上一个停留位置的累计奖励有关，于是需要记录位置。另外，要确定与上一停留位置的关系，还需要记录下每种卡片的剩余个数。
考虑用f[i, a1, a2, a3, a4]表示停留在i位置用掉的各种卡片数分别为a1、a2、a3、a4时的最大奖励数。这样，空间复杂度较大。 又注意到题目中说输入数据保证 N-1=
?bi，所以想到i可以用a1、a2、a3、a4表示，所
i?1m以简化为f[a1, a2, a3, a4]表示用掉的各种卡片数分别为a1、a2、a3、a4时的最大奖励数。 可得方程：
f[a1, a2, a3, a4] = max ( f[a1-1, a2, a3, a4] f[a1, a2-1, a3, a4]
f[a1, a2, a3-1, a4] f[a1, a2, a3, a4-1]) + c[step] step为当前停留位置，step = a1 + 2*a2+ 3*a3 + 4 * a4 + 1 【代码】
Program tortoise; Const
infile = 'tortoise.in'; outfile = 'tortoise.out'; Var
a: Array[1..4] Of Longint; i, m, n, c: Longint;
map: Array[1..350] Of Longint;
f: Array[0..40, 0..40, 0..40, 0..40] Of Longint; Function max(x, y: Longint): longint; Begin
If x > y Then Exit(x); Exit(y); End;
Procedure work(n1, n2, n3, n4: Longint); //求f[n1, n2, n3, n4] Var
step: Longint; Begin
If n1 > 0 Then Begin
If f[n1-1, n2, n3, n4] = 0 Then work(n1-1, n2, n3, n4); //递归 f[n1, n2, n3, n4] := max(f[n1, n2, n3, n4], f[n1-1, n2, n3, n4]); End;
If n2 > 0 Then Begin
If f[n1, n2-1, n3, n4] = 0 Then work(n1, n2-1, n3, n4); //递归 f[n1, n2, n3, n4] := max(f[n1, n2, n3, n4], f[n1, n2-1, n3, n4]); End;
If n3 > 0 Then Begin
If f[n1, n2, n3-1, n4] = 0 Then work(n1, n2, n3-1, n4); //递归 f[n1, n2, n3, n4] := max(f[n1, n2, n3, n4], f[n1, n2, n3-1, n4]); End;
If n4 > 0 Then Begin
If f[n1, n2, n3, n4-1] = 0 Then work(n1, n2, n3, n4-1); //递归 f[n1, n2, n3, n4] := max(f[n1, n2, n3, n4], f[n1, n2, n3, n4-1]); End;
step := 1 + n1 + 2 * n2 + 3 * n3 + 4 * n4; //求出当前位置 f[n1, n2, n3, n4] := f[n1, n2, n3, n4] + map[step]; End; Begin
Assign(input, infile); Reset(input);
Assign(output, outfile); Rewrite(output); ReadLn(n, m);
For i:=1 To n Do Read(map[i]); ReadLn;
Fillchar(a, SizeOf(a), 0); For i:=1 To m Do Begin Read(c); Inc(a[c]); End;
Fillchar(f, SizeOf(f), 0);
f[0, 0, 0, 0] := map[1]; //一张卡片都未用，即停留在1号格子时 work(a[1], a[2], a[3], a[4]);
WriteLn(f[a[1], a[2], a[3], a[4]]); Close(input); Close(output); End.