题目

Description

We say a sequence of characters is a palindrome if it is the same written forwards and backwards.
For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not.
A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence.
For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups.
Given a sequence of characters,
we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask:
what is the minimum number of groups needed for a given string such that every group is a palindrome
For example:
‘racecar’ is already a palindrome, therefore it can be partitioned into one group.
‘fastcar’ does not contain any non-trivial palindromes, so it must be partitioned as (‘f’, ‘a’, ‘s’, ‘t’, ‘c’, ‘a’, ‘r’).
‘aaadbccb’ can be partitioned as (‘aaa’, ‘d’, ‘bccb’).

Input

Input begins with the number n of test cases. Each test case consists of a single line of between 1 and
1000 lowercase letters, with no whitespace within.

Output

For each test case, output a line containing the minimum number of groups required to partition the
input into groups of palindromes.

Sample Input

3
racecar
fastcar
aaadbccb

Sample Output

1
7
3

题解

求最少的划分,使所有部分都是回文串

最初的想法是:尽可能长的划分每一部分,最后输出答案
这样有一个问题就是 bcbaabc 答案应该是 2 但是输出会是 4
局部不取最优反而能使结果最优

类似于 贪心 与 背包 的关系
因此换用 动态规划
还是仿照上面的思路
有 dp[i] = min{dp[j-1] + 1} ( j~i 是回文串)

写到这很容易,但是最后 WA 了好几发
问题在于 边界值
由于字符串从 0 开始
因此循环的时候 j-1 有可能为 -1
这是一个随机的值,本地测试的时候可能会是 0 输出正确答案,但是交上去后就只能看脸了

要解决也很简单
从 1~len 循环
判断回文串的时候将位置坐标减去 1 即可

时间复杂度是 O(n3)
不过大多数情况最后一个循环(判断回文串)是立即结束的

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int maxn = 1005;

int dp[maxn];
string s;

bool isPalindrome(int a,int b) {
    for(int it1 = a,it2 = b;it1 < it2;it1++,it2--)
        if(s[it1] != s[it2])
            return false;
    return true;
}

void Do() {
    cin >> s;
    int len = s.size();
    int ans = 0;

    dp[0] = 0;
    for(int i = 1;i <= len;i++) {
        dp[i] = dp[i - 1] + 1;
        for(int j = 1;j < i;j++)
            if(isPalindrome(j - 1,i - 1))
                dp[i] = min(dp[i],dp[j - 1] + 1);
    }

    cout << dp[len] << endl;
}

int main() {
    int T;
    cin >> T;
    for(int i = 1;i <= T;i++)
        Do();
    return 0;
}