344

题目

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.

3
racecar
fastcar
aaadbccb

1
7
3

题解

dp[i] = min{dp[j-1] + 1} ( j~i 是回文串)

1~len 循环

代码

/*
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;
}

• 点击查看/关闭被识别为广告的评论