本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 23:13:52

ABC176F Brave CHAIN题解

Link

很好的一道题。

首先考虑扔三张留两张相当于有一个大小为 $2$ 的包，每次只能装两张牌。

考虑dp。设 $f_{i,x,y}$ 表示前 $i+2$ 张牌（因为三张三张分组所以相当于枚举是哪一组），保留了 $x$ 和 $y$ 的最大收益。

首先有 $\mathrm{O(n)}$ 大常数转移做法，总复杂度 $\mathrm{O(n^3)}$ ，过不去。

首先发现若当前三张 $a=A_i,b=A_{i+1},c=A_{i+2}$ 相同则可以直接删去，容易发现是对的。

然后发现除了上一种情况，与 $a,b,c$ 无关的状态在一次转移中是不会被改变的。那么被改变的状态数就是 $\mathrm{O(n)}$ 的。

这启发我们找只与 $a,b,c$ 相关状态的转移方程。转移中重要的是 $a,b,c$ 而非 $x,y$ 。

对于 $a,b,c$ 相同的情况上面已经去掉了，不考虑。

若有两个数字 $a=a,b=a$ 相同，则若想要增加贡献则必须要找到某一个状态 $f_{i-1,x=a,c}$ 的最大值，然后再加一。

然后是一般的没有贡献的状态更新，容易发现只会跟 $a,b,c$ 相关的状态会被更新。

这两个都是 $\mathrm{O(n)}$ 级别的。

细节的，第一种是查询列最大值，第二种是查询全局最大值以及列最大值。

像背包一样压掉一维，这样才能保证不会被转移的状态不会占用复杂度。

由于两种转移可能同时发生，所以用 vector 来转移。

code

const int N=2e3+5;

int f[N][N];
int mx[N];\/\/行\/列最大值，这里这个矩阵是沿对角线对称的

int t[N*3];

struct hhh{
	int u,v,w;
};
vector<hhh>_new;

void clr(vector<hhh>&vec){
	vector<hhh>c;
	swap(c,vec);
}

signed main(){
	int n=read();
	for(int i=1;i<=3*n;i++)
		t[i]=read();
	memset(f,-0x3f,sizeof(f));
	memset(mx,-0x3f,sizeof(mx));
	mx[t[1]]=mx[t[2]]=0;
	f[t[1]][t[2]]=f[t[2]][t[1]]=0;
	int d=0;
	for(int i=3;i<3*n;i+=3){
		int a=t[i],b=t[i+1],c=t[i+2];
		if(a==b&&b==c)
			d++;\/\/全局加
		else{
			int mxx=-inf;
			for(int j=1;j<=n;j++){
				_new.pb({j,a,mx[j]});
				_new.pb({j,b,mx[j]});
				_new.pb({j,c,mx[j]});
				mxx=max(mxx,mx[j]);
			}
			_new.pb({a,b,max(mxx,f[c][c]+1)});
			_new.pb({b,c,max(mxx,f[a][a]+1)});
			_new.pb({a,c,max(mxx,f[b][b]+1)});\/\/以上是第二种转移
			if(a==b||a==c||b==c){\/\/第一种转移
				if(b==c)
					swap(a,b);
				if(a==c)
					swap(b,c);
				for(int j=1;j<=n;j++)
					_new.pb({j,c,f[a][j]+1});
			}
			for(hhh x:_new){
				f[x.u][x.v]=f[x.v][x.u]=max(f[x.u][x.v],x.w);
				mx[x.u]=max(mx[x.u],x.w);
				mx[x.v]=max(mx[x.v],x.w);
			}
			clr(_new);
		}
	}
	int ans=f[t[3*n]][t[3*n]]+1;\/\/最后两个可能会再造成一次贡献
	for(int i=1;i<=n;i++)
		ans=max(ans,mx[i]);
	print(ans+d),pc('\n');
	return 0;
}