ProjectDP - 3

枚举转移

题目背景

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

题目描述

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

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

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

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入输出格式

输入格式

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

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

第2行个非负整数，，其中表示棋盘第个格子上的分数。

第3行个整数，，表示M张爬行卡片上的数字。

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

输出格式

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

输入输出样例

输入样例

1
2
3

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

输出样例

1

73

解题思路

先来想想五维的 DP

我们设 表示当前用了 个卡片1， 个卡片2， 个卡片3， 个卡片4，走了 步时的最大得分

分别对四种卡片进行转移

考虑一下优化。
显然 是可以通过计算得出的， （注意后面的+1，因为是从第一个格开始的），那么就能省去一维

转移方程就变为了

最终答案留做习题见代码

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

//
//  3.cpp
//  ProjectDP
//
//  Created by HandwerSTD on 2019/1/25.
//  Copyright © 2019 Handwer STD. All rights reserved.
//

#include <iostream>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;
using std::max;

/*
 *
 * CARD1 means the card that can make the turtle go 1 block.
 * CARD2, CARD3 and CARD4 too.
 * dp[i][j][k][l] records the max score when there are i CARD1(s), j CARD2(s), k CARD3(s) and l CARD4(s) have been used.
 *
 * Formula:
 *     Step = i * 1 + j * 2 + k * 3 + l * 4 + 1
 *     Max = dp[i][j][k][k]
 *     Max = max(Max, dp[i-1][j][k][l]) (i >= 1)
 *     Max = max(Max, dp[i][j-1][k][l]) (j >= 1)
 *     Max = max(Max, dp[i][j][k-1][l]) (k >= 1)
 *     Max = max(Max, dp[i][j][k][l-1]) (l >= 1)
 *     dp[i][j][k][l] = Max + score[Step]
 *
 * Answer:
 *     dp[a][b][c][d],
 *     a -> the amount of CARD1, b, c, and d too.
 *
 */

const int MAXN = 350 + 10;
const int MAXM = 120 + 10;
const int MAXCARD = 40 + 10;

int n, m, sc[MAXN], cds[MAXM];
int a, b, c, d;
int dp[MAXCARD][MAXCARD][MAXCARD][MAXCARD];

int main() {
    IMPROVE_IO();
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> sc[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> cds[i];
        if (cds[i] == 1) ++a;
        if (cds[i] == 2) ++b;
        if (cds[i] == 3) ++c;
        if (cds[i] == 4) ++d;
    }
    for (int i = 0; i <= a; ++i) {
        for (int j = 0; j <= b; ++j) {
            for (int k = 0; k <= c; ++k) {
                for (int l = 0; l <= d; ++l) {
                    int walked = 1 + i * 1 + j * 2 + k * 3 + l * 4;
                    if (walked > n) break;
                    int Max = dp[i][j][k][l];
                    if (i - 1 >= 0) Max = max(Max, dp[i-1][j][k][l]);
                    if (j - 1 >= 0) Max = max(Max, dp[i][j-1][k][l]);
                    if (k - 1 >= 0) Max = max(Max, dp[i][j][k-1][l]);
                    if (l - 1 >= 0) Max = max(Max, dp[i][j][k][l-1]);
                    dp[i][j][k][l] = Max + sc[walked];
                }
            }
        }
    }
    cout << dp[a][b][c][d] << endl;
    return 0;
}