wa on

sub1 : #10 , #13 ;

sub2 : #2

#include <bits/stdc++.h>
using namespace std;
int n,f[505][505],x,prex=0,now=0,cnt=0;
struct sect{
	int num,idx;
};
sect a[505];
int main()
{
	cin>>n;
	memset(f,0x3f,sizeof(f));
  //合并相同珠子
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(i==1)
		{
			now=1;
			prex=x;
		}
		else if(x!=prex)
		{
			a[++cnt].idx=prex;
			a[cnt].num=now;	
			now=1;
			prex=x;
		}
		else
		{
			now++;
		}
	}
	a[++cnt].idx=prex;
	a[cnt].num=now;	
//区间dp
	n=cnt;
	for(int i=1;i<=n;i++)
	{
		f[i][i]=3-a[i].num;
		if(f[i][i]<0)f[i][i]=0;
	}
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			if(a[i].idx==a[j].idx)
			{
				if(a[i].num+a[j].num>=3)f[i][j]=min(f[i][j],f[i+1][j-1]);
				else f[i][j]=min(f[i][j],f[i+1][j-1]+1);
			}
			for(int k=i;k<=j-1;k++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
				if(k>i)
				{
					if(a[i].idx==a[j].idx && a[i].idx==a[k].idx)
					{
						if(a[i].num+a[k].num<3 && a[k].num+a[j].num<3)
							f[i][j]=min(f[i][j],f[i+1][k-1]+f[k+1][j-1]);
					}
				}
			}
			
		}
	}
	cout<<f[1][n];
	return 0;
}