ATCoder-[ABC176F] Brave CHAIN

ATCoder-[ABC176F] Brave CHAIN

题好我非，交了 14 遍才过，一直 RE，原因是储存修改的数组开小了，然而以为是在调用存值的时候数组越界，从下午调到晚上。

考虑暴力设计状态和转移，由于每次的五张牌中有三张来自之前，而另外两张则确定，那么我们考虑令 $dp_{i,j,k}$ 表示第 $i$ 次选牌时固定的牌为 $i,j$，那么暴力转移总时间复杂度为 $\text{O}(10\cdot n^3)$。但是我们发现其中有一部分的转移时没有必要的，我们当前的转移是和当前所取到的两个数有关，令固定的两个数为 $x,y$，其他三个数为 $a,b,c$，以下对删除后剩余的两个数进行分类讨论。（$dp$ 表示当前状态，$Lt$ 表示上次修改后的状态）

1. 剩余的两个数为 $a,b,c$ 中的任意两个数，那么与此时所取到的两个数没有任何关系，如果 $a=b=c$ 时，则所有的贡献值都会加 1，否则不变，那么此时不必更新状态。
2. 剩余的两个数为 $a,b,c$ 中的任意一个数，而另一个数则是 $x,y$ 中的一个，那么我们考虑对于状态 $dp_{i,x}=\max(Lt_{i,j},Lt_{a,a}+1)$，那么我们只需要维护一个关于 $Lt_{i,j}$ 的最大值 $s_i$。
3. 剩余的两个数为 $x,y$ 那么对于状态的转移为 $dp_{x,y}=\max\{Lt_{i,j}\}$。如果 $x=y$，那么就还有 $dp_{i,j}=\max\{Lt_{x,x}+1\}$，就再维护一个关于全局的 $\text{Max}$ 的值。

那么考虑到被单次修改的位置是 $\text{O}(n)$ 级别的，那么我们就开个数组存下每次修改的位置然后暴力修改（此处注意将数组开大一些，不然会疯狂 RE）

#include<cstdio>
#include<iostream>
#include<cctype>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e3+1e1;
const lint INF=1e18+1e9;
int qx[MAXN<<3],qy[MAXN<<3],f[MAXN],S[MAXN],a[MAXN*3];
int dp[MAXN][MAXN],Lt[MAXN][MAXN],n,Max=0,Ans=0,cnt=0;

void Update(int A,int B,int C){
	for(int i=1;i<=n;i++){
		if(S[i]>=0){
			if(dp[A][i]<S[i]) dp[A][i]=dp[i][A]=S[i];
			qx[++cnt]=A,qy[cnt]=i;
		}
		if(B==C && Lt[B][i]>=0){
			if(dp[A][i]<Lt[B][i]+1) dp[A][i]=dp[i][A]=Lt[B][i]+1;
			qx[++cnt]=A,qy[cnt]=i;
		}
	}
	if(dp[B][C]<Max) dp[B][C]=dp[C][B]=Max;
	if(Lt[A][A]>=0 && dp[B][C]<Lt[A][A]+1){
		dp[B][C]=dp[C][B]=Lt[A][A]+1;
	}
	qx[++cnt]=B,qy[cnt]=C;
	return;
}

int main(void){

	scanf("%d",&n);
	for(int i=1;i<=3*n;i++) a[i]=readint;
	for(int i=1;i<n;i++) if(a[3*i]==a[3*i+1] && a[3*i+1]==a[3*i+2]) ++f[i];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=Lt[i][j]=-inf;
	dp[a[1]][a[2]]=dp[a[2]][a[1]]=Lt[a[1]][a[2]]=Lt[a[2]][a[1]]=0;
	for(int i=1;i<=n;i++) S[i]=-inf;
	S[a[1]]=S[a[2]]=0;
	for(int i=1;i<n;i++){
		if(f[i]){Ans+=f[i];continue;}
		int A=a[3*i],B=a[3*i+1],C=a[3*i+2];
		Update(A,B,C),Update(B,A,C),Update(C,A,B);
		while(cnt){
			int x=qx[cnt],y=qy[cnt--];
			S[x]=max(dp[x][y],S[x]),S[y]=max(dp[x][y],S[y]);
			Max=max(dp[x][y],Max),Lt[x][y]=Lt[y][x]=dp[x][y];
		}
	}
	printf("%d\n",max(dp[a[3*n]][a[3*n]]+1,Max)+Ans);

	return 0;
}