Codeforces Round #336 (Div. 1) B. Zuma

题意:给你一个长度为n的数组,可以花费1个代价消去一个连续区间的回文串,消去后剩下的数组连起来.问你最少的代价消去整个数组. 思路: 对 于 消 去 区 间 [ i , j ] 的 值 , 只 需 要 讨 论 i 与 哪 个 位 置 消 掉 就 能 覆 盖 所 有 情 况 . 1. 消 去 自 己 d p ( i , j ) = 1 + d p ( i + 1 , j ) . 2. 选 择 一 个 位 置 k , 满 足 a [ i ] = = a [ k ] , 那 么 即 可 免 费 消 去 i , k 两 个 位 置 . d p ( i , j ) = d p ( i + 1 , k − 1 ) + d p ( k + 1 , j ) 但 是 上 述 情 况 会 有 特 殊 . 当 k = i + 1 时 , 第 一 项 变 为 ( i + 1 , i ) . 显 然 这 是 在 消 去 [ i , i + 1 ] , 组 成 了 一 个 新 的 回 文 串 , 需 要 新 增 一 个 费 用 , 该 费 用 不 能 从 d p ( i + 1 , k − 1 ) 处 得 到 . 所 以 特 殊 情 况 : a [ i + 1 ] = = a [ i ] 时 , 有 d p ( i , j ) = 1 + d p ( i + 2 , j ) . 对于消去区间[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). 对于消去区间[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
using namespace std;
const int maxn = 500+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair 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>a[i];
	}
	for(int i=1;i