Desciption

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片见样例），每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

Solution

看数据范围，4种爬行卡片，每种卡片的张数不会超过40，这个条件很重要，很容易想到用动态规划解决

  • 表示使用了 i张1卡，j张2卡，k张3卡，l张4卡得到的最优值

那么有转移方程

  • , 其中 为

然后我写完后发现怎么一直过不了样例，原来是我把第一个点默认是1， 那么val要改成
这样就过了。

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int num[5], a[1005];
int dp[45][45][45][45];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        num[x]++;
    } 
    dp[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 l = 0; l <= num[4]; l++) {
                    int val = a[i + 2 * j + 3 * k + 4 * l + 1];
                    if(i) {
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + val);
                    }
                    if(j) {
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + val);
                    }
                    if(k) {
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + val);
                    }
                    if(l) {
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + val);
                    }
                }
            }
        }
    }
    cout << dp[num[1]][num[2]][num[3]][num[4]] << "\n";
    return 0;
}