题解：P14413 [JOISC 2015] 有趣的卡牌游戏 / Card Game Is Great Fun

· · 题解

好题，出到集训里了，写个题解。

怎么大家的 dp 状态都是三维空间 O(n^3) 的啊，这里给一个空间 O(n^2) 的做法。

思路

我们记取第 1 张卡牌的操作为操作 A，取第 3 张卡牌的操作为操作 B。我们能够注意到，对于连续进行的操作 B，通过其取出来的卡片一定是连续的一段。

考虑我们进行一次操作 A，后面接着若干操作 B，设在进行 B 操作之前第一张卡牌的编号是 i，第二张卡牌的编号是 j，那么如果进行了 k 次 B 操作，我们得到的卡牌就是编号 j+1 到编号 j+k 的卡牌。

这个时候你发现，如果我只考虑记录下第一张卡牌和第二章卡牌的编号，好像就能直接推出来后面进行若干次 B 操作后能够得到的得分。

所以你就可以设状态 dp 了，设 f_{i,j} 表示最后一次进行的是 A 操作，并且下一次将会进行 B 操作，当前所能得到的最大得分，对于所有 j-i>1 的情况，我们有：

f_{i,j}=\max_{C_k=C_{j+1}\vee A_k=A_{j+1}}\{f_{k,i}+V_k\}

但是问题来了，这样的转移没法得到下一次进行的是 A 操作的情况，所以我们需要额外设一个状态 g_{i,j}，表示最后一次进行的是 A 操作，并且下一次将会进行 A 操作，当前所能得到的最大得分，对于所有 j-i>1 的情况，我们有：

g_{i,j}=\max_{(C_k=C_i\vee A_k=A_i)\wedge(C_k=C_{j-1}\vee A_k=A_{j-1})}\{f_{k,i}+V_k\}

有了上面两个状态，我们就能够转移 j=i+1 时的情况了：

f_{i,j}=\max_{C_k=C_{j+1}\vee A_k=A_{j+1}}\{g_{k,i}+V_k\}\\~\\ g_{i,j}=\max_{C_k=C_i\vee A_k=A_i}\{g_{k,i}+V_k\}

对于答案，你可以枚举对于每种状态后面会进行多少次 B 操作，是 naive 的。

这四种转移单次显然只需要枚举 k 即可，总时间复杂度为 O(n^3)。

代码

:::success[代码]

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=505;
const ll INF=2147483647;
ll f[N][N],g[N][N],pre[N],n,C[N],A[N],V[N],sum[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>C[i]>>A[i]>>V[i];
    for(ll i=1;i<=n;i++) sum[i]=sum[i-1]+V[i];
    ll ans=0;
    for(ll i=1;i<=n;i++){
        if(A[i]==A[i-1]||C[i]==C[i-1]) pre[i]=pre[i-1];
        else pre[i]=i;
        if(pre[i]==1) ans=max(ans,sum[i]);
    }
    for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) g[i][j]=f[i][j]=-INF;
    for(ll i=1;i<=n;i++){
        for(ll j=i+1;j<=n;j++){
            if(i==1&&j==2) g[i][j]=f[i][j]=0;
            else{
                if(j==i+1){
                    for(ll k=1;k<i;k++){
                        if(g[k][i]==-INF) continue;
                        if(A[k]==A[j+1]||C[k]==C[j+1]) f[i][j]=max(f[i][j],g[k][i]+V[k]);
                        if(A[k]==A[i]||C[k]==C[i]) g[i][j]=max(g[i][j],g[k][i]+V[k]);
                    }
                }
                else{
                    if(pre[j-1]>i+1) continue;
                    for(ll k=1;k<i;k++){
                        if(f[k][i]==-INF) continue;
                        if(!(A[k]==A[j-1]||C[k]==C[j-1])) continue;
                        if(A[k]==A[j+1]||C[k]==C[j+1]) f[i][j]=max(f[i][j],f[k][i]+V[k]+sum[j-1]-sum[i]);
                        if(A[k]==A[i]||C[k]==C[i]) g[i][j]=max(g[i][j],f[k][i]+V[k]+sum[j-1]-sum[i]);
                    }
                }
            }
            for(ll k=j+1;k<=n;k++){
                if(pre[k]<=j+1){
                    ans=max(ans,f[i][j]+sum[k]-sum[j]);
                    if(A[k]==A[i]||C[k]==C[i]){
                        ans=max(ans,f[i][j]+sum[k]-sum[j]+V[i]);
                        if(A[i]==A[j]||C[i]==C[j]) ans=max(ans,f[i][j]+sum[k]-sum[j]+V[i]+V[j]);
                    }
                }
                else break;
            }
            ans=max(ans,g[i][j]+V[i]);
            if(j==n){
                if(A[i]==A[j]||C[i]==C[j]) ans=max(ans,g[i][j]+V[i]+V[j]);
            }
        }
    }
    cout<<ans;
    return 0;
}

:::