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;
}