d273: 11584 - Partitioning by Palindromes
Tags : DP
Accepted rate : 77人/91人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-05-22 09:46

Content

迴文的定義就是從左邊寫跟有右邊寫 都一樣 ,例如 'racecar'就是一個迴文,'fastcar'則不是。

 給你一個字串,我們可以找到很多長度不同的迴文字串,任務就是找到把一個字串分成許多小字串,是每一個小字串都是迴文,並找出最少分幾堆。

例如:

        'racecar'已經是一個迴文,所以他只需要分成一堆。

        'fastcar'  沒有一個迴文的部分,所以她必須分成('f', 'a', 's', 't', 'c', 'a', 'r')

         'aaadbccb' 則可以分成 ('aaa', 'd', 'bccb').

 

Input

第一行代表有幾組測資,每一行包含1~1000個小寫子母,沒有任何的空白夾在裡面。 

Output


對於每一個測試資料,輸出最少可以分成幾堆,使每堆都是迴文。
 
Sample Input
3
racecar
fastcar
aaadbccb

Sample Output
1
7
3

測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
DP
出處:
UVa11584 [管理者:
nanj0178 (nanj)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」