2009 Chopsticks

ずいぶんと短いソースになるんですね、それから区間DPなんですが意外な形の区間DPであった。
この制約はオーダーが複数の候補になって考えるのに多少時間がかかる。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[301][301];
char str[301];
int main(){
	int a;
	scanf("%d%s",&a,str);
	for(int i=0;i<301;i++)
		for(int j=0;j<301;j++)
			dp[i][j]=99999999;
	for(int i=a-1;i>=0;i--){
		dp[i][i]=1;
		for(int j=i;j<a-1;j++){
			for(int k=j+1;k<a;k++){
				dp[i][k]=min(dp[i][k],dp[i][j]+dp[j+1][k]);
			}
			if(str[i]==str[j+1])dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
		}
	}
	printf("%d\n",dp[0][a-1]);
}