【题目标题】NOIP2010乌龟棋

【题目大意】

一行$N$个格子，每个格子有一个权值。棋子一开始在起点，有$M$张让棋子向前走的卡，分别是$1$步、$2$步、$3$步、$4$步。求用光所有卡后获得的最大权值。

数据保证用完$M$张卡后刚好达到第$N$格

【算法分析】

本题采用动态规划。

考虑记录使用完每种卡片具体张数后的得分情况。

设定变量$num$，$num[i]$表示第$i$个格子的分值。

设定变量$f$， $f[a][b][c][d]$表示用了$a$张一步卡，$b$张两步卡，$c$张三步卡，$d$张四步卡获得的最大分数。

则$f[a][b][c][d]$是由上一张使用的什么卡所决定，且已知$a、b、c、d$的情况下，可求出位于哪一个格子。

则可得状态转移方程
$f[a][b][c][d] = num[1+a+b*2+c*3+d*4]+max(f[a-1][b][c][d], f[a][b-1][c][d], f[a][b][c-1][d], f[a][b][c][d-1])$

初始状态为
$f[0][0][0][0] = num[1]$

【参考代码】

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int f[41][41][41][41], num[351], g[5], n, m, x;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	f[0][0][0][0] = num[1];
	for (int i = 1; i <= m; i++)
	{
		cin >> x;
		g[x]++;
	}
	for (int a = 0; a <= g[1]; a++)
		for (int b = 0; b <= g[2]; b++)
			for (int c = 0; c <= g[3]; c++)
				for (int d = 0; d <= g[4]; d++)
				{
					int r = 1 + a + b * 2 + c * 3 + d * 4;
					if (a)
						f[a][b][c][d] = max(f[a][b][c][d], num[r] + f[a - 1][b][c][d]);
					if (b)
						f[a][b][c][d] = max(f[a][b][c][d], num[r] + f[a][b - 1][c][d]);
					if (c)
						f[a][b][c][d] = max(f[a][b][c][d], num[r] + f[a][b][c - 1][d]);
					if (d)
						f[a][b][c][d] = max(f[a][b][c][d], num[r] + f[a][b][c][d - 1]);
				}
	cout << f[g[1]][g[2]][g[3]][g[4]];
	return 0;
}

【时间复杂度】

$O(K^4)$，$K$为卡片张数，$K <= 40$

【预计得分】

$100pts$