首页 > itarticle > cf 608d zuma 区间dp

cf 608d zuma 区间dp

admin 11月 12, 2020 0

题意

给出$nleft( 1le nle 500 right)$的整数序列,每次可以选取一个回文区间消去.求最少的次数可以消去整个序列.

对于一个区间[l,r]如果a[l]==a[r]则这个区间的消去可以等于[l+1,r-1]的消去次数(因为a[l]与a[r]可以与[l+1,r-1]内的某个序列一起消去.所以可以区间dp~

using namespace std;
const int maxn = 510;
int dp[maxn][maxn],a[maxn];
int (int l,int r){
	int ret = r-l+1;
	if(dp[l][r]!=-1)return dp[l][r];
	if(l>=r)return dp[l][r]=1;
	if(a[l] == a[r])ret = min(ret,f(l+1,r-1));
	for(int i=l;i<r;++i)ret = min(ret,f(l,i)+f(i+1,r));
	return dp[l][r]=ret;
}
int main(){
	memset(dp,-1,sizeof(dp));
	int n=0;
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	f(1,n);
	cout<<dp[1][n]<<endl;
	return 0;
}