Codeforces Round #336 (Div. 1) B.Zuma(区间dp/删回文串求删完的最少次数)

题目

n(n<=500)个数，第i个数为ci(1<=ci<=n)

每次你可以删掉一个回文子串，删掉这段之后，后面的会接上来，

问最少需要多少次，可以全部删完

思路来源

https://blog.csdn.net/shremier_zer/article/details/79406854

题解

dp[l][r]代表删掉[l,r]最少需要多少段，

首先，是经典的划分点拆成子问题，分成dp[l][k]和dp[k+1][r]分别删两段

其次，如果a[l]==a[r]，

考虑[l+1,r-1]这一段，里面的这段最后删的回文子串一定包含端点l+1或r-1，

这意味着，可以把a[l]和a[r]补在[l+1,r-1]这段最后删的回文子串两侧，次数不变

回文子串只需要考虑回文增量即可，故无别的转移可能

形如abbxa先删bb再删axa的跨越操作，

实际是bbx拆成bb和x最终这一段值为2，而两个a补在了x两侧，使答案仍为2

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int n,a[N],dp[N][N]; 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		dp[i][i]=1;
		if(i){
			if(a[i-1]==a[i])dp[i-1][i]=1;
			else dp[i-1][i]=2;
		}
	}
	for(int len=3;len<=n;++len){
		for(int l=1;l+len-1<=n;++l){
			int r=l+len-1;
			dp[l][r]=n;
			for(int k=l;k<r;++k){//枚举划分点 分成两段删 
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
			}
			if(a[l]==a[r])dp[l][r]=min(dp[l][r],dp[l+1][r-1]);//注意递推关系 在原有回文串外侧补两个字母
			//考虑子区间最后删的回文串一定包含某个端点 
			//printf("dp[%d][%d]:%d\n",l,r,dp[l][r]);
		}
	}
	printf("%d\n",dp[1][n]);
	return 0;
}