【题目标题】NOIP2010乌龟棋
【题目大意】
一行NNN个格子，每个格子有一个权值。棋子一开始在起点，有MMM张让棋子向前走的卡，分别是111步、222步、333步、444步。求用光所有卡后获得的最大权值。
数据保证用完MMM张卡后刚好达到第NNN格
【算法分析】
本题采用动态规划。
考虑记录使用完每种卡片具体张数后的得分情况。
设定变量numnumnum，num[i]num[i]num[i]表示第iii个格子的分值。
设定变量fff， f[a][b][c][d]f[a][b][c][d]f[a][b][c][d]表示用了aaa张一步卡，bbb张两步卡，ccc张三步卡，ddd张四步卡获得的最大分数。
则f[a][b][c][d]f[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[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[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]f[0][0][0][0] = num[1]f[0][0][0][0]=num[1]
【参考代码】
【时间复杂度】
O(K4)O(K^4)O(K 4 )，KKK为卡片张数，K<=40K <= 40K<=40
【预计得分】
100pts100pts100pts
