清華集訓(xùn)2017模擬之字符串 - 全文

　　Description　　

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

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

　　Input

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

　　接下來(lái)一行一個(gè)長(zhǎng)度為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

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

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

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

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

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

　　Solution

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

　　這有50分

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

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

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

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

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

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

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

Code

　　#include《cstdio》

　　#include《cstring》

　　#include《algorithm》

　　#define fo（i，a，b） for（int i=a;i《=b;i++）

　　#define fd（i，a，b） for（int i=a;i》=b;i--）

　　#define N 101000

　　using namespace std;

　　int n，K，a［N］［27］，f［N］［27］，s［N］，bz［27］，ans;

　　int main（）

　　{

　　scanf（“%d%d\n”，&n，&K）;

　　fo（i，1，n）

　　{

　　char c=getchar（）;

　　s［i］=c-97;

　　}

　　fo（k，1，26）

　　{

　　memset（bz，0，sizeof（bz））;

　　int x=0，y=0;

　　while（y《=k&&x《=n）

　　{

　　x++;

　　bz［s［x］］++;if（bz［s［x］］==1） y++;

　　}

　　a［0］［k］=x-1;

　　fo（i，2，n+1）

　　{

　　bz［s［i-1］］--;if（bz［s［i-1］］==0） y--;

　　while（y《=k&&x《=n）

　　{

　　x++;

　　bz［s［x］］++;if（bz［s［x］］==1） y++;

　　}

　　a［i-1］［k］=x-1;

　　}

　　}

　　memset（f，255，sizeof（f））;

　　f［0］［0］=0;

　　fo（k，0，26）

　　{

　　fo（i，0，K-1）

　　if（f［i］［k］》=0）

　　{

　　fo（k1，1，26-k） f［i+1］［k+k1-1］=min（n-K+i+1，max（f［i+1］［k+k1-1］，a［f［i］［k］］［k1］））;

　　}

　　}

　　fd（k，26，0） if（f［K］［k］==n） ans=k+K;

　　printf（“%d\n”，ans）;

　　}