URAL/1635

来自"NOCOW"

DP,O(n^2)即可。

#include <iostream>
#include <cstring>
using namespace std;
int n,tot=0,a[4001]={0},b[4001]={0},c[4001]={0},d[4001]={0},f[4001]={0},g[4002]={0};
char s[4003]={'\0'};
int main()
{
    cin >> &s[1];
    n=strlen(&s[1]);
    for (int i=1;i<=n;++i)
    {
        int l=i,r=i;
        while ((s[l] == s[r]) && l && (r <= n))
        {
            ++a[i];
            --l,++r;
        }
        l=i,r=i+1;
        while (l && (r <= n) && (s[l] == s[r]))
        {
            ++b[i];
            --l,++r;
        }
    }
    for (int i=1;i<=n;++i)
    {
        f[i]=f[i-1]+1;
        c[i]=i-1;
        for (int j=i+1>>1;j;--j)
        {
            int p=i-(j<<1)+1,q=i-((j<<1)-1>>1);
            if (a[q] >= j)
                if (f[p]+1 < f[i])
                {
                    f[i]=f[p]+1;
                    c[i]=p;
                }
            p=i-(j<<1),q=i-j;
            if (p < 0)  continue;
            if (b[q] >= j)
                if (f[p]+1 < f[i])
                {
                    f[i]=f[p]+1;
                    c[i]=p;
                }
        }
    }
    cout << f[n] << endl;
    while (n)
    {
        g[++tot]=n;
        n=c[n];
    }
    while (tot)
    {
        for (int i=g[tot+1]+1;i<=g[tot];++i)
            cout << s[i];
        cout << ' ';
        --tot;
    }
    cout << endl;
    return 0;
}
//by zzy