P1541 乌龟棋

题目描述

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N,M$，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行 $N$ 个非负整数，$a_1,a_2,\dots ,a_N$，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数，$b_1,b_2,\dots ,b_M$，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。

$1\le N\le 350,1\le M\le 120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0\le a_i\le 100,1\le i\le N,1\le b_i\le 4,1\le i\le M$。

输出格式

一个整数，表示小明最多能得到的分数。

Solution

多维 DP

int f[45][45][45][45];
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int num[5] = {};
    for (int i = 1;i <= m;i++) {
        int x;cin >> x;num[x]++;
    }
    f[0][0][0][0] = a[1];
    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 p = 0;p <= num[4];p++) {
                    int r = 1 + i + 2 * j + 3 * k + 4 * p;
                    if (i)f[i][j][k][p] = max(f[i][j][k][p], f[i - 1][j][k][p] + a[r]);
                    if (j)f[i][j][k][p] = max(f[i][j][k][p], f[i][j - 1][k][p] + a[r]);
                    if (k)f[i][j][k][p] = max(f[i][j][k][p], f[i][j][k - 1][p] + a[r]);
                    if (p)f[i][j][k][p] = max(f[i][j][k][p], f[i][j][k][p - 1] + a[r]);
                }
            }
        }
    }
    cout << f[num[1]][num[2]][num[3]][num[4]] << '\n';
}