codeforces 835D 区间dp

简单的区间dp

dp[i][j] 表示区间i-j的回文度数

转移方程就是在 si=sj且dp[i+1][j−1]>0 时 dp[i][j]=dp[i+1][(i+j)/2]+1

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
#define LL long long
int dp[][];
int main()
{
    char str[];
    while(scanf("%s",str)!=EOF)
    {
        clr(dp);
        int len = strlen(str);
        int ans[] = {};
        for(int i = ;i<len;i++)
            dp[i][i] = ,ans[]++;
        for(int i = ;i<len;i++)
        {
            for(int j = ;j<len-i;j++)
            {
                if(i&) // 偶数个
                {
                    if(i==)
                    {
                        if(str[j]==str[j+i])
                        {
                            dp[j][j+i] = ;
                            ans[]++;
                        }
                    }
                    else
                    {
                        int l = j+;
                        int r = j+i-;
                        if(str[j] == str[j+i] && dp[l][r]>)
                        {
                            dp[j][j+i] = dp[j][j+i/]+;
                            ans[dp[j][j+i]]++;
                        }
                    }
                }
                else // 奇数个
                {
                    int l = j+;
                    int r = j+i-;

                    if(str[j]==str[j+i] && dp[l][r]>)
                    {
                        dp[j][j+i] = dp[j][j+i/-]+;
                        ans[dp[j][j+i]]++;
                    }
                }
                //cout << j << " " << j+i << " num " << dp[j][j+i] << endl;
            }
        }
        //cout << dp[2][4] << endl;
        for(int i = len-;i>=;i--)
        {
            ans[i] = ans[i]+ans[i+];
        }
        for(int i = ;i<=len;i++)
        {
            if(i!=)printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return ;
}