# [jsoi2007]祖码zuma（洛谷2145）

Posted by yjjr's blog on February 6, 2018

9

1 1 2 2 3 3 2 1 1

1

F[l][r]表示从l->R最少用珠子次数，先预处理出color[i]和num[i]记录原来珠子序列

Color数组从前往后记录原珠子中不同颜色

Num数组和color数组一一对应，表示不同颜色的珠子的个数

f[l][r]=min(f[l][i]+f[i+1][r],f[i][j]);

code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=506,inf=0x3f3f3f;
struct node{int num,col;}b[maxn];
int n,cnt,now,num,a[maxn],f[maxn][maxn];
int main(){
scanf("%d",&n);
rep(i,1,n)scanf("%d",&a[i]);
mem(f,inf);
int now=a[1],cnt=0,num=0;
rep(i,1,n){
if(a[i]!=now){
b[++cnt].num=num;
b[cnt].col=now;
num=1;
now=a[i];
}
else num++;
if(i==n){
b[++cnt].num=num;
b[cnt].col=now;
}
}
rep(i,1,cnt){
if(b[i].num>1)f[i][i]=1;
else f[i][i]=2;
}
rep(p,2,cnt)
rep(i,1,cnt-p+1){
int j=i+p-1;
if(b[i].col==b[j].col){
if(b[i].num+b[j].num==2)
f[i][j]=f[i+1][j-1]+1;
else f[i][j]=f[i+1][j-1];
}
rep(k,i,j-1)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
printf("%d\n",f[1][cnt]);
return 0;
}