题解 | #小美和大富翁#

四张牌每次用一张考虑状压

dp[1111][i] 代表人在第 i 位且四张牌都有的情况下的最优答案

dp[1010][i] 代表人在第 i 位只有4，2号牌的情况下的最优答案

不难发现在任意位置，能转移而来的情况只有最大 15 种，我们可以直接遍历所有情况，然后判断是否存在一个合法的历史情况，如果存在，那就转移

这道题也是只转移合法情况的题，如果使用数组的话要初始化成-1来标记不合法情况，我这里使用map实现，只转移合法情况，就可以避免标记

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int __t = 1, n, a[N];
void solve() {
    cin >> n;
    map<int, map<int, int>> dp;
    dp[15][0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 1; j < 16; j++) {
            for (int k = 1; k <= 4 && i - k >= 0; k++) {
                if ((1 << (k - 1)) & j) {
                    int nj = j ^ (1 << (k - 1));
                    if (nj == 0)
                        nj = 15;
                    if (dp[j].count(i - k) && dp[j][i - k] + a[i] >= 0)
                        dp[nj][i] = max(dp[nj][i], dp[j][i - k] + a[i]);
                }
            }
        }
    }
    int ans = -1;
    for (int i = 1; i < 16; i++)
        if (dp[i].count(n))
            ans = max(ans, dp[i][n]);
    cout << ans << "\n";
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __t;
    while (__t--)
        solve();
    return 0;
}