hdu 4632 Palindrome subsequence

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【重做DP系列】 字符串DP,记忆化搜索实现

【2013多校联合训练第四场】

题意:给定一个字符串,找出里面有多少个回文子序列

dp[i][j]表示i到j之间有多少个回文子序列,目标状态是dp[0][n-1]

不取前一个字符能产生的回文子序列,dp[i+1][j]

不取后一个字符能产生的回文子序列,dp[i][j-1]

不取前后两个字符能产生的回文子序列,dp[i+1][j-1]

那么 dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1],减去是因为减掉重复的部分

如果str[i] = str[j],那么加上这两个依然是一个回文串

dp[i][j] += ( dp[i+1][j-1] + 1)

这是个区间dp,递推和递归实现都可以,递推快一些,递归容易理解容易写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1010
#define MOD 10007
#define cl(xx,yy) memset((xx),yy,sizeof((xx)))

int n,dp[N][N];
char str[N];

void dfs(int x,int y){
if(dp[x][y] != -1) return ;
if(x > y)
dp[x][y] = 0;
else if(x == y)
dp[x][y] = 1;
else if(x + 1 == y){
if(str[x] != str[y])
dp[x][y] = 2;
else dp[x][y] = 3;
}
else{
dfs(x+1,y);
dfs(x,y-1);
dfs(x+1,y-1);
dp[x][y] = (dp[x+1][y] + dp[x][y-1] - dp[x+1][y-1] + MOD) % MOD;
if(str[x] == str[y]) dp[x][y] = (dp[x][y] + dp[x+1][y-1] + 1) % MOD;
}
}

int main(){
int T;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
scanf("%s",str);
n = strlen(str);
cl(dp,-1);
dfs(0,n-1);
printf("Case %d: %d\n",cas,dp[0][n-1]);
}
return 0;
}