hdu 4632 子字符串统计的区间dp

题意：查找这样的子回文字符串（未必连续，但是有从左向右的顺序）个数。

简单的区间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; 这里不忘记，新加入的和结尾构成的情况。

PS：弱菜还需努力！下面俩点注意。

#include<iostream>

#include<string>

#include<cstdio>

#include<cstring>

using namespace std;

long long  dp[1005][1005];

int main()

{

    int T;

    cin>>T;

    string s;int cs=1;

    while(T--)

    {

        cin>>s;

        //memset(dp,0,sizeof(dp));

        int len=s.size();

       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]+10007-dp[j+1][i-1])%10007;  //  注意1，当有减法的时候，取模要加个模！否则负数！

                if(s[i]==s[j])

                dp[j][i]=(dp[j][i]+dp[j+1][i-1]+1)%10007;  //注意2：取模的时候不要用+=

            }

        }

      printf("Case %d: %d\n",cs++,dp[0][len-1]);

    }

    return 0;

}

巴特西

hdu 4632 子字符串统计的区间dp

最新文章

热门文章