首页 > 代码库 > HDU 4632 Palindrome subsequence(区间dp,回文串,字符处理)

HDU 4632 Palindrome subsequence(区间dp,回文串,字符处理)

题目

 

 

参考自博客:http://blog.csdn.net/u011498819/article/details/38356675

 

 

题意:查找这样的子回文字符串(未必连续,但是有从左向右的顺序)个数。

简单的区间dp,哎,以为很神奇的东西,其实也是dp,只是参数改为区间,没做过此类型的题,想不到用dp,以后就

知道了,若已经知道【0,i】,推【0,i+1】, 显然还要从i+1 处往回找,dp方程也简单: 
dp[j][i]=(dp[j+1][i]+dp[j][i-1]+10007-dp[j+1][i-1])%10007; 减去中间一段重复的 
if(s[i]==s[j])dp[j][i]=(dp[j][i]+dp[j+1][i-1]+1)%10007;  这里不忘记,新加入的和结尾构成的情况。

 

 

#include<stdio.h>#include<string.h>#include<algorithm>#include<string>#include<iostream>using namespace std;int dp[1010][1010];//dp[i][j]  i~j之间的回文串数目int main(){    int t;    scanf("%d",&t);    for(int id=1;id<=t;id++)    {        char s[1010];        scanf("%s",s);        int len=strlen(s);        memset(dp,0,sizeof(dp));        for(int i=0;i<len;i++)            dp[i][i]=1;        for(int i=0;i<len;i++)        {            for(int j=i-1;j>=0;j--)            {                //当有减法的时候,取模要加个模!否则负数!                dp[j][i]=(dp[j+1][i]+dp[j][i-1]-dp[j+1][i-1]+10007)%10007;//忘记模了。。。                if(s[i]==s[j])                    dp[j][i]=(1+dp[j+1][i-1]+dp[j][i])%10007;//忘记模了。。。            }        }        printf("Case %d: %d\n",id,dp[0][len-1]%10007);    }    return 0;}
View Code