题解 | 小美和大富翁

看题意第一时间想到使用动态规划来解：遍历每一个下标的值，统计移动到该下标的金币总和最大值。

因为每轮次给定4张卡值分别是1、2、3、4，且必须用完才可以获取下一轮的卡，那么在动规的维度就需要考虑下标与剩余卡值，比如下标为3的点，可以是直从0点使用3号卡0->3,可以是从0点使用1号卡再使用2号卡0->1->3，所以只有相同下标与相同剩余卡值的才能进行比较，为了方便比较，这里使用二进制作为卡值表示0001、0010、0100、1000分别表示1、2、3、4号卡，每次使用以后与取反值进相与。同时为了方便查找，这里使用map作为dp容器。

遍历到的每个点，其下一步的移动目标都会有多种可能，所以需要把每一种可能都枚举出来，并计算由移动到该点的金币最大值f(n)，因为到达n点具有最多4种情况(实际上可能会少于4种)，所以是取f(n-1)、f(n-2)、f(n-3)、f(n-4)的最大值与该点金币值G(n)的和值。

反向计算不太好想像，这里还是用正向推导，遍历当前点，推导其下一步可能达到的点的最大值，所以起步需要从0点开始（数组插入前置0值）。最后需要判断中途是否存在无法达到的点（金币值小于0），如果下一个点不可达，那么dp集合中就不会存在这个点的值，因为计算过程中每一个点都可能会跳过，但前置条件是四张卡都必须使用完才可以进入下一轮，那么就是每一轮必须是十个点，那只需要计算每一轮最后一个点是否可达即可。

#include <cstdio>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
    int k ;
    cin >> k;
    vector<int> vec;
    int b ;
    while (cin >> b) { // 注意 while 处理多个 case
        vec.push_back(b);
    }
    vec.insert(vec.begin(), 0);
    int n = vec.size();
    int cards = 0b00001111;
    unordered_map<int, unordered_map<int, long long>> m;
    m[0][cards] = 0;
    int next;
    long long value;
    for (int i = 0; i < n; i++) {
        if (m[i].size() <= 0) {
            if (i % 10) {
                continue;
            }
            printf("%lld\n", -1LL);
            return 0;
        }
        for (auto mp : m[i]) {
            if (mp.first & 0b00001000 && i + 4 < n) {
                if ((value = mp.second + vec[i + 4]) >= 0) {
                    next = mp.first & 0b11110111;
                    next = next ? next : cards;
                    m[i + 4][next] = std::max(m[i + 4][next], value);
                }
            }
            if (mp.first & 0b00000100 && i + 3 < n) {
                if ((value = mp.second + vec[i + 3]) >= 0) {
                    next = mp.first & 0b11111011;
                    next = next ? next : cards;
                    m[i + 3][next] = std::max(m[i + 3][next], mp.second + vec[i + 3]);
                }
            }
            if (mp.first & 0b00000010 && i + 2 < n) {
                if ((value = mp.second + vec[i + 2]) >= 0) {
                    next = mp.first & 0b11111101;
                    next = next ? next : cards;
                    m[i + 2][next] = std::max(m[i + 2][next], mp.second + vec[i + 2]);
                }
            }
            if (mp.first & 0b00000001 && i + 1 < n) {
                if ((value = mp.second + vec[i + 1]) >= 0) {
                    next = mp.first & 0b11111110;
                    next = next ? next : cards;
                    m[i + 1][next] = std::max(m[i + 1][next], mp.second + vec[i + 1]);
                }
            }
        }
    }
    long long max = 0;
    for (auto mp : m[n - 1]) {
        max = std::max(max, mp.second);
    }
    printf("%lld", max);
    return 0;
}
// 64 位输出请用 printf("%lld")