专栏文章

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

xxixisuper九倍体水稻
P14413题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min33gvz
此快照首次捕获于
2025/12/01 19:46
3 个月前
此快照最后确认于
2025/12/01 19:46
3 个月前
查看原文
好题，出到集训里了，写个题解。
怎么大家的 dp 状态都是三维空间 O(n3)O(n^3) 的啊，这里给一个空间 O(n2)O(n^2) 的做法。

思路

我们记取第 1 张卡牌的操作为操作 AA，取第 3 张卡牌的操作为操作 BB。我们能够注意到，对于连续进行的操作 BB，通过其取出来的卡片一定是连续的一段。
考虑我们进行一次操作 AA，后面接着若干操作 BB，设在进行 BB 操作之前第一张卡牌的编号是 ii，第二张卡牌的编号是 jj，那么如果进行了 kk 次 BB 操作，我们得到的卡牌就是编号 j+1j+1 到编号 j+kj+k 的卡牌。
这个时候你发现，如果我只考虑记录下第一张卡牌和第二章卡牌的编号，好像就能直接推出来后面进行若干次 BB 操作后能够得到的得分。
所以你就可以设状态 dp 了，设 fi,jf_{i,j} 表示最后一次进行的是 AA 操作，并且下一次将会进行 BB 操作，当前所能得到的最大得分，对于所有 j−i>1j-i>1 的情况，我们有：
fi,j=max⁡Ck=Cj+1∨Ak=Aj+1{fk,i+Vk}f_{i,j}=\max_{C_k=C_{j+1}\vee A_k=A_{j+1}}\{f_{k,i}+V_k\}
但是问题来了，这样的转移没法得到下一次进行的是 AA 操作的情况，所以我们需要额外设一个状态 gi,jg_{i,j}，表示最后一次进行的是 AA 操作，并且下一次将会进行 AA 操作，当前所能得到的最大得分，对于所有 j−i>1j-i>1 的情况，我们有：
gi,j=max⁡(Ck=Ci∨Ak=Ai)∧(Ck=Cj−1∨Ak=Aj−1){fk,i+Vk}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+1j=i+1 时的情况了：
fi,j=max⁡Ck=Cj+1∨Ak=Aj+1{gk,i+Vk} gi,j=max⁡Ck=Ci∨Ak=Ai{gk,i+Vk}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\}
对于答案，你可以枚举对于每种状态后面会进行多少次 BB 操作，是 naive 的。
这四种转移单次显然只需要枚举 kk 即可，总时间复杂度为 O(n3)O(n^3)。

代码

代码CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...