题解 | #小美和大富翁#

//dp 以十个十个为单位，f[i][j]表示到第i个城市，用的牌的组合为j，j用1~15表示，二进制的四位表示四张牌，然后线性dp即可

#include <iostream>
#include <vector>
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int maxn = 1e5+10;
ll f[maxn][16];
int main() {
    int n;
    scanf("%d",&n);
    vector<ll>A(n+1,0);
    for(int i =1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    memset(f,-1,sizeof(f));
    f[0][0] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<16;j++){
            int cur = 1;
            int d =0;
            while(cur<=4){
                if(j&(1<<(cur-1))){
                    d+=cur;
                }
                cur++;
            }
            // if(i==4){
            //     printf("j:%d  d:%d\n",j,d);
            // }
            int turn_dis = i%10;
            if(turn_dis == 0)   turn_dis = 10;   
            if(d!=turn_dis)   continue;
            // if(d>turn_dis)   break;    
            // printf("turndis:%d\n",turn_dis);
            cur = 1;
            while(cur<=4){
                if(j&(1<<(cur-1))){
                    int pre = j^(1<<(cur-1));
                    // printf("i:%d j:%d cur:%d  pre:%d\n",i,j,cur,pre);
                    // printf("f[i-cur][pre]:%lld\n",f[i-cur][pre]);
                    if(f[i-cur][pre]!=-1&&f[i-cur][pre]+A[i]>=0)    
                        f[i][j] = max(f[i-cur][pre]+A[i],f[i][j]);
                    // printf("%d\n")
                }
                cur++;
            } 
            // printf("i:%d j:%d,f[i][j]:%lld\n",i,j,f[i][j]);
        }
        if(i%10==0){
            f[i][0] = f[i][15];
        }
    }
    ll ans = -1;
    for(int i = 0;i<=15;i++)
        ans = max(ans,f[n][i]);
    printf("%lld\n",ans);
        // printf("%lld\n",f[n][])
}
// 64 位输出请用 printf("%lld")