题目地址：

space=1&num=1635">Ural 1635

又是输出路径的DP。。。连着做了好多个了。

。

状态转移还是挺简单的。要先预处理出来全部的回文串，tag[i][j]为1表示字符串i--j是一个回文串。否则不是回文串。预处理时要用n^2的方法。即枚举回文串中间。能够分奇数和偶数两种分别求一次。

然后dp转移方程为,若tag[j][i]==1,dp[i]=min(dp[i],dp[j-1]+1);

对于最令人讨厌的路径输出。能够用pre来记录回文串前驱分裂点，然后依据这些分裂点来输出。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define LL __int64

const int INF=0x3f3f3f3f;

char s[5000];

int dp[5000], tag[4001][4001], len, pre[4001], a[4001];

void init()

{

    int i, j, k, l, r;

    memset(tag,0,sizeof(tag));

    for(i=0;i<len;i++)

        tag[i][i]=1;

    for(i=1;i<len;i++)

    {

        for(j=1;j<=i;j++)

        {

            l=i-j;r=i+j;

            if(r>=len) break;

            if(s[l]==s[r])

            {

                tag[l][r]=1;

            }

            else break;

        }

    }

    for(i=0;i<len-1;i++)

    {

        if(s[i]==s[i+1])

        {

            tag[i][i+1]=1;

            for(j=1;j<=i;j++)

            {

                l=i-j;r=i+j+1;

                if(r>=len) break;

                if(s[l]==s[r])

                {

                    tag[l][r]=1;

                }

                else

                    break;

            }

        }

    }

}

int main()

{

    int i, j, k, cnt;

    scanf("%s",s);

    len=strlen(s);

    init();

    dp[0]=0;

    memset(pre,-1,sizeof(pre));

    for(i=1;i<=len;i++)

    {

        dp[i]=dp[i-1]+1;

        pre[i]=i-1;

        for(j=1;j<i;j++)

        {

            if(tag[j-1][i-1])

            {

                if(dp[i]>dp[j-1]+1)

                {

                    dp[i]=dp[j-1]+1;

                    pre[i]=j-1;

                }

            }

        }

    }

    printf("%d\n",dp[len]);

    cnt=0;

    for(i=len;i!=-1;i=pre[i])

    {

        a[++cnt]=i;

        //printf("%d ",a[cnt-1]);

    }

    sort(a+1,a+cnt+1);

    /*for(i=1;i<=cnt;i++)

    {

        printf("%d ",a[i]);

    }*/

    for(i=2;i<=cnt;i++)

    {

        for(j=a[i-1];j<a[i];j++)

        {

            printf("%c",s[j]);

        }

        if(i!=cnt)

        printf(" ");

        else

            puts("");

    }

    return 0;

}