Description
给定一串数字,每个数字代表一种颜色
你可以向这个数字序列里加任意数字,每加一个视为一次操作
当你加入的数字和与它相连的同种数字不少于三个时,他们就会消除
消除后序列的两端自动靠拢合并
求使得整个序列完全消失的最少操作次数
Analysis
一道区间 DP
注意本题的几个点
即使给出的序列中已经有连续的不少于三个的相同数字,也必须向其中再加入一个才能删去
消除一段序列后,再靠拢的序列两端如果又可以拼出不少于三个的序列,此时是可以消去的
如果还不明白,可以现在去玩一玩祖玛
考虑怎么表示想要消除某种数字的连续序列应该放几个数字
(col[]) 表示当前位置是那种数字
然后想办法把输入的连续同种数字填进同一个位置,(val[])记录它的个数
因为将每连续的数字放到同一个位置并记录种类和数量后,对于消除某个数字连续的序列,就变成了消除他所在的那一个位置
而消除的方法就是使其数量大于等于三
Solution
(f[i][j]) 表示消除从第 (i) 个位置到第 (j) 个位置的序列需要的最少操作数
所以就有状态转移方程
而且上面说了消除完合并后的如果合法也会消除
因此判断一下,当 (col[i]=col[j]) 时
因为要取最小值,所以要有预处理
当数字的数量为1时,需要再放两个数字才能消除,所以 (f[i][i]=1)
同理,数字的数量 (ge) 2 时,只需再放一个,此时 (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 即可