回文串+回溯法 URAL 1635 Mnemonics and Palindromes

题目传送门

/*
    题意：给出一个长为n的仅由小写英文字母组成的字符串，求它的回文串划分的元素的最小个数，并按顺序输出此划分方案
    回文串+回溯：dp[i] 表示前i+1个字符(从0开始)最少需要划分的数量，最大值是i+1，即单个回文串；
        之前设置ok[j][j+i] 判断从j到j+i的字符是否为回文串(注意两个for的顺序，为满足ok[j][j+i] = ok[j+1][j+i-1])
        最后枚举找到最优划分点，用pre[i]记录前一个位置，print函数 输出空格
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 4e3 + 10;
const int INF = 0x3f3f3f3f;
int dp[MAXN];
int pre[MAXN];
bool ok[MAXN][MAXN];
char s[MAXN];

void print(int p)
{
    if (pre[p] == -1)
    {
        for (int i=0; i<=p; ++i)    printf ("%c", s[i]);
    }
    else
    {
        print (pre[p]);    printf (" ");
        for (int i=pre[p]+1; i<=p; ++i)    printf ("%c", s[i]);
    }
}

void work(void)
{
    int len = strlen (s);

    for (int i=0; i<len; ++i)
    {
        for (int j=0; j+i<len; ++j)
        {
            if (i == 0)    ok[j][j+i] = true;
            else if (i == 1)    ok[j][i+j] = (s[j] == s[j+i]);
            else if (s[j] == s[j+i])    ok[j][j+i] = ok[j+1][j+i-1];
        }
    }

    for (int i=0; i<len; ++i)
    {
        dp[i] = i + 1;    pre[i] = i - 1;
        if (ok[0][i])    {dp[i] = 1;    pre[i] = -1;    continue;}
        for (int j=i-1; j>=0; --j)
        {
            if (ok[j+1][i])
            {
                if (dp[i] > dp[j] + 1)
                {
                    dp[i] = dp[j] + 1;    pre[i] = j;
                }
            }
        }
    }

    printf ("%d
", dp[len-1]);
    print (len-1);    puts ("");
}

int main(void)        //URAL 1635 Mnemonics and Palindromes
{
    //freopen ("P.in", "r", stdin);

    while (scanf ("%s", s) == 1)
    {
        memset (ok, false, sizeof (ok));
        memset (dp, 0, sizeof (dp));
        memset (pre, 0, sizeof (pre));

        work ();
    }

    return 0;
}