【每日一题】乌龟棋

题目

乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片），每种类型的卡片上分别标有 1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。
游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。
玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
求最多能得多少分？

解题思路

动态规划：

表示使用了 张 1 卡片， 张 2 卡片， 张 3 卡片， 张 4 卡片的最大分数。
此时，乌龟棋子所在位置是 。
所以 。
初始时，没有使用卡片时，，即起点的分数。

C++代码

#include<iostream>
#include<vector>
using namespace std;

const int maxm = 45;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> score(N);
    for(int i=0; i<N; ++i){
        cin >> score[i];
    }
    int num[5] = {0};
    int kind;
    for(int i=0; i<M; ++i){
        cin >> kind;
        num[kind] += 1;
    }
    int f[maxm][maxm][maxm][maxm];
    f[0][0][0][0] = score[0];
    for(int i=0; i<=num[1]; ++i){
        for(int j=0; j<=num[2]; ++j){
            for(int k=0; k<=num[3]; ++k){
                for(int t=0; t<=num[4]; ++t){
                    int tmp = 0;
                    if(i>0)
                        tmp = max(tmp, f[i-1][j][k][t]);
                    if(j>0)
                        tmp = max(tmp, f[i][j-1][k][t]);
                    if(k>0)
                        tmp = max(tmp, f[i][j][k-1][t]);
                    if(t>0)
                        tmp = max(tmp, f[i][j][k][t-1]);
                    int pos = i + 2*j + 3*k + 4*t;
                    f[i][j][k][t] = tmp + score[pos];
                }
            }
        }
    }
    cout << f[num[1]][num[2]][num[3]][num[4]] << endl;
    return 0;
}