乌龟棋

原题来自维基OI

题目描述:

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物.乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数).棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点.

乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1、2、3、4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数.游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次.游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数.玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和.很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多.现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

输入描述:

输入的每行中两个数之间用一个空格隔开.第1行2个正整数N和M,分别表示棋盘格子数和爬行卡片数.第2行N个非负整数,a1a2……aN,其中ai表示棋盘第i个格子上的分数.第3行M个整数,b1b2……bM,表示M张爬行卡片上的数字.输入数据保证到达终点时刚好用光M张爬行卡片.

输出描述:

输出一行一个整数,为最多能得的分数.

大概思路:

用a[i]储存第i个格子的分数.

用b[1]表示1卡有几,用b[2]表示2卡有几张...

用f[i][j][k][l]来表示用了i张1卡,j张2卡,k张3卡,l张4卡时的最大分数,最终的答案就是f[b[1]][b[2]][b[3]][b[4]].

可以得出:f[i][j][k][l] = max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+a[i+2*j+3*k+4*l+1]

f[i-1][j][k][l]是前1格格子走过来的分数,f[i][j-1][k][l]是前2个格子走过来的分数...

a[i+2*j+3*k+4*l+1]是当前位置的分数,之所以要加1,是因为一开始就在起点1的位置.

AC代码如下:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n, m, a[355] = {0}, b[5] = {0,0,0,0,0}, f[41][41][41][41]  = {0};
int max4(int i, int j, int k, int l)//4个数字的最大值max4
{
    return max(max(i, j),max(k,l));
}
int dp(int i, int j, int k, int l)
{
    if (i<0 || j<0 || k<0 || l<0)//这四个数必须是非负的
        return 0;
    else if (f[i][j][k][l])//如果已经求过了就直接返回
        return f[i][j][k][l];
    else
    {
        f[i][j][k][l] = max4(dp(i-1,j,k,l),dp(i,j-1,k,l),dp(i,j,k-1,l),dp(i,j,k,l-1));
        f[i][j][k][l] += a[i+2*j+3*k+4*l+1];
        return f[i][j][k][l];
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1, t; i <= m; i++)
    {
        cin >> t;
        b[t]++;
    }
    memset(f, 0, sizeof(f));//先把所有的设置为0表示,都没求过
    f[0][0][0][0] = a[1];
    cout << dp(b[1],b[2],b[3],b[4]);
    return 0;
}

如果有什么不合理之处,敬请批评指正.