清華集訓2017模擬之字符串

　　Description　　

一個字符串的權(quán)值是這個串包含的不同字符個數(shù)。

　　給定一個長度為n的字符串，把它分為k個連續(xù)非空字段，每個字符必須在某一段中，最小化字符串的權(quán)值和。

　　Input

　　第一行兩個數(shù)n，k，含義如題所述。

　　接下來一行一個長度為n的字符串，保證僅包含小寫英文字母。

　　Output

　　輸出最小權(quán)值。

　　Sample Input

　　輸入1：

　　12 3

　　abaacdddfe

　　輸入2：

　　50 35

　　acbdcfabcaedscdbcsbacbdcbbacjacbkabcjadkcbsjkckkza

　　Sample Output

　　輸出1：

　　6

　　樣例解釋1：

　　一種最優(yōu)方案是分為：”abaa”， “cddd”和”feff”。

　　輸出2：

　　39

　　Data Constraint

　　對于10%的數(shù)據(jù)，n《=10。

　　對于30%的數(shù)據(jù)，n《=200。

　　對于50%的數(shù)據(jù)，n《=1500。

　　對于另外20%的數(shù)據(jù)，僅包含a和b兩種字母。

　　對于100%的數(shù)據(jù)，1《=k《=n《=100，000。

　　Solution

　　一個很顯然的dp：f［i］［j］表示到位置i，分為了j段，需要的最小代價

　　這有50分

　　可以發(fā)現(xiàn)，答案最大為段數(shù)+25

　　那么代價不會很大，可以放到狀態(tài)中

　　狀態(tài)改成f［i］［j］表示分了i段，代價為i+j最右可以到哪里

　　預處理一個a［i］［j］表示從位置i出發(fā)，花代價為j，最右可以到哪里

　　然后隨意轉(zhuǎn)移一下

　　但是，這么做是有bug的（數(shù)據(jù)里沒有，所以這樣就可以A了）

　　如果到某一次，最后剩下的位數(shù)已經(jīng)不夠分K段了，前面就不能延伸到最后，這個取個min就行了