ZZULIOJ1526-小L的项链切割(最少回文个数DP)

发布于 2019-08-15  404 次阅读


问题传送门:

题意:

把一个字符串切割成最少的回文串个数
求切割的次数,
也就是最少有几个回文串,再减一。
给出的字符串最长是1000.

分析:

一开始想的是贪心,每次找出最长的那个回文串。
仔细想想就能发现这种思路的错误:
虽然找到了最长的一个回文,但是可能多出了两个回文。
正确的方法应该是动态规划。
dp[i] 表示的是字符串 S[0~i] 最少被划分成几个回文串。
这样,从头遍历一遍字符串,
如果S[0~i] 是回文串,dp[i] = 0
如果S[0~i]不是回文串,先令dp[i] = i+1, 然后是难点:
j 从 1~i,依次判断 S[j~i] 是不是回文串:
如果S[j~i] 是回文串,dp[i] = min(dp[i], dp[j-1] + 1)
如果S[j~i]不是回文串,dp[i] = min(dp[i], dp[j-1] + i-j+1)
 
我判断是否是回文串是最一般的O(n) 的方法,那么整个算法就是O(n^3)
但这个是最坏的情况下,这个题数据没有那么严格,也AC了。
最完美的方法是用字符串Hash的方法去判断是不是回文。
但是。目前不会。。。

代码:

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

const int MAXN = 1e3+10;
int dp[MAXN];

bool Judge(string s)
{
    int L = 0;
    int R = s.length() - 1;
    while (L < R)
    {
        if (s[L] == s[R])
            L++, R--;
        else 
            return false;
    }
    return true;
}

int main()
{
    int T, len;
    string s;
    cin >> T;
    while (T--)
    {
        cin >> s;
        len = s.length();
        for (int i = 0; i < len; i++)
            dp[i] = 0;
        for (int i = 0; i < len; i++)
        {
            if (Judge(s.substr(0,i+1))) 
            {
                dp[i] = 1;
                continue;
            }
            dp[i] = i+1;
            for (int j = 1; j <= i; j++) 
            {
                if (Judge(s.substr(j, i-j+1)))
                    dp[i] = min(dp[i], dp[j-1]+1);
                else 
                    dp[i] = min(dp[i], dp[j-1]+i-j+1);
            }
        }
        cout << dp[len-1]-1 << endl;
    }
    return 0;
}

Simple And Clear