2011-09-09 20:07:54Morris
d273. 11584 - Partitioning by Palindromes
d273. 11584 - Partitioning by Palindromes
作法 : DP
首先建立 : S[i]~S[j] 是否是一個迴文的字串,
接著, 開始著手 DP
DP[i] = min (DP[j-1] + 1) when s[j] - s[i] 是個迴文
DP[i] 表示 s[0~i] 的最少迴文數量
/**********************************************************************************/
/* Problem: d273 "11584 - Partitioning by Palindromes" from UVA11584 */
/* Language: C */
/* Result: AC(0ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-09 19:55:23 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 1002
char map[1001][1001];
int Build(char *s) {
int i, j, k, l = strlen(s);
memset(map, 0, sizeof(map));
for(i = 0; i < l; i++) {
j = i, k = i;
while(j >= 0 && k < l && s[j] == s[k]) {
map[j][k] = 1;
j--, k++;
}
}
for(i = 0; i < l-1; i++) {
j = i, k = i+1;
while(j >= 0 && k < l && s[j] == s[k]) {
map[j][k] = 1;
j--, k++;
}
}
}
int procee_DP(char *s) {
int DP[1001] = {}, l = strlen(s);
int i, j;
DP[0] = 1;
for(i = 1; i < l; i++) {
DP[i] = oo;
for(j = 0; j <= i; j++) {
if(map[j][i]) {
if(j != 0)
DP[i] = DP[i] < DP[j-1]+1 ? DP[i] : DP[j-1]+1;
else
DP[i] = 1;
}
}
}
return DP[l-1];
}
main() {
int t;
char s[1001];
scanf("%d", &t);
while(t--) {
scanf("%s", s);
Build(s);
printf("%d\n", procee_DP(s));
}
return 0;
}
內容 ：
迴文的定義就是從左邊寫跟有右邊寫 都一樣 ，例如 'racecar'就是一個迴文，'fastcar'則不是。
給你一個字串，我們可以找到很多長度不同的迴文字串，任務就是找到把一個字串分成許多小字串，是每一個小字串都是迴文，並找出最少分幾堆。
例如：
'racecar'已經是一個迴文，所以他只需要分成一堆。
'fastcar' 沒有一個迴文的部分，所以她必須分成('f', 'a', 's', 't', 'c', 'a', 'r')
'aaadbccb' 則可以分成 ('aaa', 'd', 'bccb').
輸入說明 ：
第一行代表有幾組測資，每一行包含1~1000個小寫子母，沒有任何的空白夾在裡面。
輸出說明 ：
對於每一個測試資料，輸出最少可以分成幾堆，使每堆都是迴文。
範例輸入 ：
3racecarfastcaraaadbccb
範例輸出 ：
173
提示 ：
出處 ：
UVA11584 (管理：nanj0178)
作法 : DP
首先建立 : S[i]~S[j] 是否是一個迴文的字串,
接著, 開始著手 DP
DP[i] = min (DP[j-1] + 1) when s[j] - s[i] 是個迴文
DP[i] 表示 s[0~i] 的最少迴文數量
/**********************************************************************************/
/* Problem: d273 "11584 - Partitioning by Palindromes" from UVA11584 */
/* Language: C */
/* Result: AC(0ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-09 19:55:23 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 1002
char map[1001][1001];
int Build(char *s) {
int i, j, k, l = strlen(s);
memset(map, 0, sizeof(map));
for(i = 0; i < l; i++) {
j = i, k = i;
while(j >= 0 && k < l && s[j] == s[k]) {
map[j][k] = 1;
j--, k++;
}
}
for(i = 0; i < l-1; i++) {
j = i, k = i+1;
while(j >= 0 && k < l && s[j] == s[k]) {
map[j][k] = 1;
j--, k++;
}
}
}
int procee_DP(char *s) {
int DP[1001] = {}, l = strlen(s);
int i, j;
DP[0] = 1;
for(i = 1; i < l; i++) {
DP[i] = oo;
for(j = 0; j <= i; j++) {
if(map[j][i]) {
if(j != 0)
DP[i] = DP[i] < DP[j-1]+1 ? DP[i] : DP[j-1]+1;
else
DP[i] = 1;
}
}
}
return DP[l-1];
}
main() {
int t;
char s[1001];
scanf("%d", &t);
while(t--) {
scanf("%s", s);
Build(s);
printf("%d\n", procee_DP(s));
}
return 0;
}