abc176F题解

abs176F
题意:
给定长度为\(3\times n\)，值域是\([1,n]\)的序列，不断下列操作直至序列剩余\(3\)个数：
1.对序列最左侧\(5\)个数进行任意排列。
2.取出序列最左侧\(3\)个数，如果\(3\)个数一样，则得分加一，然后删除这三个数。
问最大得分为多少。
思路：
神仙dp题。
首先有一个显然的\(\Theta(n^3)\)dp。状态\(f_{i,j,k}\)表示进行完\(i\)次操作后，最左侧两个数是\(j\)和\(k\)。转移是\(\Theta (1)\)的。
这里有单调性，\(f_{i-1,j,k}\le f_{i,j,k}\)。所以并不用将所有的{j,k}全部转移，下面让我们看看有哪些转移：
能有\(3\)个一样的:
1.当\(a_3=a_4=a_5\)，对于所有的\(1\le j,k\le n\)，\(f_{i-1,j,k}+1\to f_{i,j,k}\)，无其他转移，因为是全局加一，可以打一个全局tag。转移\(\Theta(1)\)。
2.当\(a_{3\sim 5}\)中有两个相等，且等于\(k\)，设\(a_{3\sim 5}\)中与其他两个不等的是\(x\)，对于所有的\(1\le j,k\le n\)，\(f_{i-1,j,k}+1\to f_{i,j,x}\)，这里设\(g_{i,j}=\max_{1\le k\le n} f_{i,j,k}\)。转移\(\Theta(1)\)，转移数量\(\Theta(n)\)。
3.当\(j=k\)，且\(a_{3\sim 5}\)中有一个与\(j\)相等，\(f_{i-1,a_3,a_3}+1\to f_{i,a_4,a_5}\)，其余同理，转移\(\Theta(1)\)，转移数量\(\Theta(1)\)。
没有\(3\)个一样的:
1.把\(a_{3\sim 5}\)都放到最左侧的\(3\)个，对于所有的\(1\le j,k\le n\)，\(f_{i-1,j,k}\to f_{i,j,k}\)，对于这里，我们可以把第一维滚掉，就不需要转移了。
2.恰好把\(a_{3\sim 5}\)中的两个放在最左侧的\(3\)个，如把\(a_3\)，\(a_4\)放在最左侧，则对于任意的\(1\le j,k\le n\)，\(f_{i-1,j,k}\to f_{i,j,a_5}\)，通过前面定义的\(g_{i,j}\)，这里的转移是\(\Theta(1)\)，转移数量是\(Theta(n)\)的。
3.恰好把\(a_{3\sim 5}\)中的一个放在最左侧的\(3\)个，如把\(a_3\)放在最左侧，则对于任意的\(1\le j,k\le n\)，\(f_{i-1,j,k}\to f_{i,a_3,a_4}\)，这里设\(h_i=\max_{1\le j,k\le n} f_{i,j,k}\)。转移\(\Theta(1)\)，转移数量\(\Theta(1)\)。
总复杂度\(\Theta(n^2)\)。
代码:

#include<iostream>
using namespace std;
int n;
int a[6010];
int f[2010][2010];
int g[2010];
struct node{
	int x,y,zhi;
}dui[2000010];
int cnt;
int add;
int sy;
int main(){
	cin>>n;
	for(int i=1;i<=3*n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=-n;
		}
		g[i]=-n;
	}
	f[a[1]][a[2]]=0;
	f[a[2]][a[1]]=0;
	g[a[1]]=0;
	g[a[2]]=0;
	sy=0;
	for(int i=1;i<n;i++){
		cnt=0;
		if(a[i*3]==a[i*3+1]&&a[i*3]==a[i*3+2]){
			add++;
			continue;
		}
		if(a[i*3]>a[i*3+1]){
			swap(a[i*3],a[i*3+1]);
		}
		if(a[i*3+1]>a[i*3+2]){
			swap(a[i*3+1],a[i*3+2]);
		}
		if(a[i*3]>a[i*3+1]){
			swap(a[i*3],a[i*3+1]);
		}
		if(a[i*3]==a[i*3+1]){
			for(int j=1;j<=n;j++){
				if(j!=a[i*3]){
					dui[++cnt].x=a[i*3+2];
					dui[cnt].y=j;
					dui[cnt].zhi=f[a[i*3]][j]+1;
					dui[++cnt].x=j;
					dui[cnt].y=a[i*3+2];
					dui[cnt].zhi=f[a[i*3]][j]+1;
				}
			}
		}
		if(a[i*3+1]==a[i*3+2]){
			for(int j=1;j<=n;j++){
				if(j!=a[i*3+1]){
					dui[++cnt].x=a[i*3];
					dui[cnt].y=j;
					dui[cnt].zhi=f[a[i*3+1]][j]+1;
					dui[++cnt].x=j;
					dui[cnt].y=a[i*3];
					dui[cnt].zhi=f[a[i*3+1]][j]+1;
				}
			}
		}
		for(int j=1;j<=3;j++){
			dui[++cnt].x=a[i*3+1];
			dui[cnt].y=a[i*3+2];
			dui[cnt].zhi=f[a[i*3]][a[i*3]]+1; 
			dui[++cnt].x=a[i*3+2];
			dui[cnt].y=a[i*3+1];
			dui[cnt].zhi=f[a[i*3]][a[i*3]]+1;
			int tmp=a[i*3];
			a[i*3]=a[i*3+1];
			a[i*3+1]=a[i*3+2];
			a[i*3+2]=tmp;
		}
		for(int j=1;j<=n;j++){
			for(int k=0;k<=2;k++){
				dui[++cnt].x=a[i*3+k];
				dui[cnt].y=j;
				dui[cnt].zhi=g[j];
				dui[++cnt].x=j;
				dui[cnt].y=a[i*3+k];
				dui[cnt].zhi=g[j];
			}
		}
		for(int j=0;j<=2;j++){
			for(int k=0;k<=2;k++){
				if(j!=k){
					dui[++cnt].x=a[i*3+j];
					dui[cnt].y=a[i*3+k];
					dui[cnt].zhi=sy;
				}
			}
		}
		for(int j=1;j<=cnt;j++){
			f[dui[j].x][dui[j].y]=max(f[dui[j].x][dui[j].y],dui[j].zhi);
			g[dui[j].x]=max(g[dui[j].x],dui[j].zhi);
			g[dui[j].y]=max(g[dui[j].y],dui[j].zhi);
			sy=max(sy,dui[j].zhi);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans=max(ans,f[i][j]+(i==a[3*n]&&j==a[3*n]));
		}
	}
	cout<<ans+add;
	return 0;
}