Codeforces Round #336 (Div. 2) D. Zuma

时间:2024-08-17 19:33:44

Codeforces Round #336 (Div. 2) D. Zuma

  • 题意:输入一个字符串;每次消去一个回文串,问最少消去的次数为多少?
  • 思路:一般对于可以从中间操作的,一般看成是从头开始(因为只需要考虑一边),当考虑最左边的数时,有多少中消去方法?每种消去方法对结果的贡献又是多少?同时结果的区间又是怎么变化?这就是dp式子;

1.当单独消去这个元素时,dp[l][r] = 1 + dp[l+1][r];

2.当存在一个k,l< k <= r,使得c[l] == c[k]时,可以认为在中间消除到只剩下一个回文串时,“顺带”把这一对元素消除;因为只少消到只剩下一个元素,那这个元素也是一个回文串,这时dp式子就是 dp[l][r] = dp[l+1][k-1] + dp[k+1][r];

那么当这里面的元素本来就为0呢?这就是我前面k的取值范围没有包括l的原因,这就是把[l , l + 1]当成回文串来消去,dp[l][r] = 1+dp[l+2][r];

// 必须说一下,我的dp思想真是弱爆了,还是看了文字题解才知道。。。

下面是我自己的代码:

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)
#define MAXN 510
int c[MAXN];
int dp[MAXN][MAXN];
int main()
{
int i,j,k,n;
cin>>n;
rep(i,n) scanf("%d",c+i);
for(i = 0;i < n;i++){ //i表示区间长度;
for(j = 0;j < n - i;j++){
dp[j][j+i] = min(i + 1,1+dp[j+1][j+i]);
if(c[j] == c[j+1])
dp[j][j+i] = min(dp[j][j+i],1+dp[j+2][j+i]);
for(k = j + 2;k <= j + i;k++)if(c[j] == c[k])
dp[j][j+i] = min(dp[j][j+i],dp[j+1][k-1] + dp[k+1][j+i]);
}
}
printf("%d",dp[0][n-1]);
}