[数据结构与算法]Codeforces Round #336 (Div. 1) B. Zuma

题意:给你一个长度为n的数组,可以花费1个代价消去一个连续区间的回文串,消去后剩下的数组连起来.问你最少的代价消去整个数组.
思路:$对于消去区间[i,j]的值,只需要讨论i与哪个位置消掉就能覆盖所有情况.1.消去自己dp(i,j)=1+dp(i+1,j).2.选择一个位置k,满足a[i]==a[k],那么即可免费消去i,k两个位置.dp(i,j)=dp(i+1,k?1)+dp(k+1,j)但是上述情况会有特殊.当k=i+1时,第一项变为(i+1,i).显然这是在消去[i,i+1],组成了一个新的回文串,需要新增一个费用,该费用不能从dp(i+1,k?1)处得到.所以特殊情况:a[i+1]==a[i]时,有dp(i,j)=1+dp(i+2,j).$
代码：

/*
  B. Zuma
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int a[maxn];int dp[maxn][maxn];
int main(){
//	freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) dp[i][j]=1;
			else if(i>j) dp[i][j]=0;
			else dp[i][j] = INF; 
		}
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j = i+len-1;
			dp[i][j] = min(dp[i][j],1+dp[i+1][j]);
			if(a[i]==a[i+1]) dp[i][j]=min(dp[i][j],1 + dp[i+2][j]);
			for(int k=i+2;k<=j;k++){
				if(a[i]==a[k]) dp[i][j] = min(dp[i][j],dp[i+1][k-1]+dp[k+1][j]);
			}
		}
	}
	cout<<dp[1][n]<<"\n";
}