电竞胡司令

每个测试点仅包含一组输入数据。
第一行一个整数 $n(1 \leq n \leq 1000)$ ，表示初始的序列长度。
接下来一行n个非负整数，第i个整数 $a_i(1 \leq a_i \leq 1000)$ 表示左起第i个珠子的颜色。
保证不存在三颗相邻的同色珠子。

C++11(clang++ 3.9) 解法, 执行用时: 2027ms, 内存消耗: 8292K, 提交时间: 2020-05-30 13:43:07

#include<bits/stdc++.h>
using namespace std;
const int N=1002;
int n,a[N],f[N][N],g[N][N];
int main(){
	scanf("%d",&n);
	memset(f,0x1f,sizeof(f));
	memset(g,0x1f,sizeof(g));
	f[1][0]=0;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		f[i][i]=2,f[i+1][i]=0;
	}
	for(int i=1;i<n;++i)
		f[i][i+1]=1+(a[i]!=a[i+1])*3;
	for(int i=3;i<=n;++i)
		for(int j=n-i+1;j;--j){
			int l=j,r=j+i-1,&u=f[l][r],&v=g[l][r];
			for(int k=l;k<r;++k)
				if(a[k]!=a[k+1]) u=min(u,f[l][k]+f[k+1][r]);
			for(int k=l+1;k<r;++k)
				if(a[k-1]!=a[k]&&a[k+1]!=a[k]&&a[k]==a[l-1]) v=min(v,f[l][k-1]+f[k+1][r]);
			if(a[l]!=a[r]) continue;
			if(a[l]!=a[l+1]&&a[r]!=a[r-1]) u=min(u,f[l+1][r-1]+1);
			if(a[l]==a[l+1]&&a[r]!=a[r-1]) u=min(u,f[l+2][r-1]);
			if(a[l]!=a[l+1]&&a[r]==a[r-1]) u=min(u,f[l+1][r-2]);
			if(a[l]!=a[l+1]&&a[r]!=a[r-1])
				for(int k=l+2;k<r-1;++k)
					if(a[l]==a[k]&&a[k]!=a[k-1]&&a[k]!=a[k+1])
						u=min(u,f[l+1][k-1]+f[k+1][r-1]);
			if(i==3) continue;
			if(a[l]==a[l+1]&&a[r]==a[r-1]) u=min(u,f[l+2][r-2]);
			if(a[l]==a[l+1]&&a[r]!=a[r-1])
				for(int k=l+2;k<r-1;++k)
					if(a[l]==a[k]&&a[k]!=a[k-1]&&a[k]!=a[k+1])
						u=min(u,f[l+2][k-1]+f[k+1][r-1]);
			if(a[l]!=a[l+1]&&a[r]==a[r-1])
				for(int k=l+2;k<r-1;++k)
					if(a[l]==a[k]&&a[k]!=a[k-1]&&a[k]!=a[k+1])
						u=min(u,f[l+1][k-1]+f[k+1][r-2]);
			if(a[l]!=a[l+1]&&a[r]!=a[r-1])
				for(int p=l+2;p<r-1;++p){
					if(a[p]==a[l]&&a[p]==a[p+1]) u=min(u,f[l+1][p-1]+f[p+2][r-1]);
					if(a[p]==a[l]&&a[p-1]!=a[p]&&a[p+1]!=a[p])
						u=min(u,f[l+1][p-1]+g[p+1][r-1]);
				}
		}
	printf("%d",f[1][n]);
	return 0;
}

详情