做题时间：2022.9.28
\(【题目描述】\)
给定一排 \(N\) 个整数，可以向之间插入任意一个整数，得到相邻的多于2个相同的整数就可以把他们消除掉，其余整数按顺序合并起来，也可以继续消除（一开始就连续的3个及以上的整数是不能消除的），问最少插入多少个整数使得所有整数都被消除完。
\(【输入格式】\)
第一行一个整数 \(N\)
第二行 \(N\) 个整数 \(a_i\)
\(【输出格式】\)
一行一个整数表示答案
\(【考点】\)
区间dp
\(【做法】\)
消除后剩余的整数连接成一个连续的区间，因此可以使用区间dp，首先可以将原序列相邻的相同的整数合并到 \(s_i\) 和 \(c_i\) 中（\(s_i\) 表示数的大小，\(c_i\) 表示数的个数），定义 \(f_{i,j}\) 表示消除 \([i,j]\) 的最小代价。首先，可以通过两个区间消除合并得到，即：
\[f_{i,j}=\min(f_{i,k}+f_{k+1,j}) \]其次，若 \(s_i=s_j\)，表示 \([i+1,j-1]\) 这一段消除后可以合并 \(s_i,s_j\) 再进行消除，即：
\[f_{i,j}=\min(f_{i+1,j-1}+(c_i+c_j\leq2)) \]\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=550;
int f[N][N],a[N],n;
int s[N],cnt[N],ed;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
s[++ed]=a[1],cnt[1]=1;
for(int i=2;i<=n;i++){
if(a[i]==a[i-1]) cnt[ed]++;
else{
s[++ed]=a[i];
cnt[ed]=1;
}
}
memset(f,63,sizeof f);
for(int i=1;i<=ed;i++){
if(cnt[i]>1) f[i][i]=1;
else f[i][i]=2;
}
for(int len=2;len<=ed;len++){
for(int i=1;i<=ed-len+1;i++){
int j=i+len-1;
if(s[i]==s[j]) f[i][j]=min(f[i][j],f[i+1][j-1]+(cnt[i]+cnt[j]<=2));
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
}
}
if(f[1][ed]==3) printf("2\n");
else printf("%d\n",f[1][ed]);
return 0;
}