记录编号	560089	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO21Feb Gold]Modern Art 3	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.574 s
提交时间	2021-04-09 22:55:24	内存使用	3.46 MiB

#include<bits/stdc++.h>
using namespace std;
int n,a[310],dp[310][310];
int main(){
	freopen("art.in","r",stdin);
	freopen("art.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=1;
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
			int j=i+len-1;
			dp[i][j]=1e+9;
			if(a[i]==a[j]){
				dp[i][j]=dp[i][j-1];
			}
				for(int k=i;k<j;k++){
					dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
				}
		}
	}
	cout<<dp[1][n]; 
}