Description
给定一串数字，每个数字代表一种颜色
你可以向这个数字序列里加任意数字，每加一个视为一次操作
当你加入的数字和与它相连的同种数字不少于三个时，他们就会消除
消除后序列的两端自动靠拢合并
求使得整个序列完全消失的最少操作次数
Analysis
一道区间 DP
注意本题的几个点
考虑怎么表示想要消除某种数字的连续序列应该放几个数字
$col[]$ 表示当前位置数字
然后想办法把输入的连续同种数字填进同一个位置，$val[]$记录它的个数
因为将每连续的数字放到同一个位置并记录种类和数量后，对于消除某个数字连续的序列，就变成了消除他所在的那一个位置
而消除的方法就是使其数量大于等于三
Solution
$f[i][j]$ 表示消除从第 $i$ 个位置到第 $j$ 个位置的序列需要的最少操作数
所以就有状态转移方程
$${f[i][j]=\min(f[i][j],f[i][k]+f[k+1][j])i\le k\le j}$$
而且上面说了消除完合并后的如果合法也会消除
因此判断一下，当 $col[i]=col[j]$ 时
设 $A=f[i+1][j-1]+0 (val[i]+val[j]>2)$
设 $B=f[i+1][j-1]+1 (val[i]+val[j]\le2)$
$${f[i][j]=\min(f[i][j],f[i+1][j-1]+ A\ \text{or}B)}$$
因为要取最小值，所以要有预处理
当数字的数量为 $1$ 时，需要再放两个数字才能消除，所以 $f[i][i]=1$
同理，数字的数量 $\ge2$ 时，只需再放一个，此时 $f[i][i]=2$
剩下的赋为极大值便可
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 510
using namespace std;
int n,ans,cnt;
int col[maxn],val[maxn],f[510][510];
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
int Min(int x,int y){return x<y?x:y;}
int main(){
n=read();
memset(f,63,sizeof f);
for(int i=1;i<=n;i++) col[i]=read();
for(int i=1;i<=n;i++){
if(i!=1&&col[i]==col[i-1]) val[cnt]++;//
else{col[++cnt]=col[i];val[cnt]=1;}
}
for(int i=1;i<=n;i++) f[i][i]=val[i]>1?1:2;
for(int s=2;s<=cnt;s++){
for(int i=1,j=i+s-1;j<=cnt;i++,j++){
if(col[i]==col[j]) f[i][j]=Min(f[i][j],f[i+1][j-1]+(val[i]+val[j]>2?0:1));
for(int k=i;k<j;k++) f[i][j]=Min(f[i][j],f[i][k]+f[k+1][j]);
}
}
printf("%d",f[1][cnt]-3==0?2:f[1][cnt]);
return 0;
}
关于第十一个数据点，据说数据有误，所以需特判才可过
当输出为 $3$ 时改为 $2$ 即可
End.
