结果

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+32;

inline int max(int a,int b,int d,int c){return max(max(a,b),max(d,c));}
inline int max(int a,int b,int c){return max(a,max(b,c));}

inline long long read_int(){
	long long x=0;bool f=0;char c=getchar();
	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}

int n,sj[maxn],tot=0,js[maxn],dp[maxn][maxn];
inline void read(){
	n=read_int();int f=0;
	for(int i=1;i<=n;i++){
		int a=read_int();
		if(a!=f) ++tot,sj[tot]=a;
		js[tot]++,f=a;
	}
	for(int i=0;i<maxn;i++) for(int e=0;e<maxn;e++) dp[i][e]=1e9;
	for(int i=1;i<=tot;i++) dp[i][i]=(js[i]>=2 ? 1 : 2);
	for(int i=2;i<=tot;i++){
		for(int e=1;(e+i-1)<=tot;e++){
			int j=(e+i-1);
			if(sj[e]==sj[j]){
				dp[e][j]=min(dp[e][j],dp[e+1][j-1]+(js[e]+js[j]>=3 ? 0 : 1));
			}
			for(int k=e;k<j;k++) dp[e][j]=min(dp[e][j],dp[e][k]+dp[k+1][j]);
		}
	}
	printf("%d\n",dp[1][tot]==3 ? 2 : dp[1][tot]);
}

int main (){
//	freopen("P2145.in","r",stdin);
	read();
}