题目链接
题目大意：给一个字符串，把它分为ｋ块，例如字符串“helloworld”分成2块，”hello”, “world”每一块里面的字母可以任意的排序。最终字符串， 连续的一样的字母算作一个chunk，问总chunks最少是多少？
解题报告：dp[i][j]表示第i块以字母j结尾
dp[i][j]=min( dp[i-1][k]+sz-1 )
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int maxn = 1010;vector<int> G[maxn];
char ch[maxn];
int dp[maxn][30];
bool vis[maxn][30]; int main(){int T;scanf("%d", &T );while( T-- ){memset(vis,0,sizeof(vis));int k;scanf("%d%s", &k, ch+1 );int n=strlen(ch+1);for ( int i=1; i<=n/k; i++ ) G[i].clear();for ( int i=1; i<=n; i++ ){int bl=(i-1)/k+1;int c=ch[i]-'a'+1;if( !vis[bl][c] ) G[bl].push_back(c);vis[bl][c]=1; }n=n/k;memset(dp,0x3f3f3f3f,sizeof(dp) );for ( int i=0; i<G[1].size(); i++ ) dp[1][G[1][i]]=G[1].size();for ( int i=2; i<=n; i++ )for ( int j=0; j<G[i].size(); j++ ){int c1=G[i][j];for ( int k=0; k<G[i-1].size(); k++ ){int c2=G[i-1][k];int sz=G[i].size();if( vis[i][c2] && (( sz>1 && c1!=c2) || (sz==1)) ){dp[i][c1]=min(dp[i][c1],dp[i-1][c2]+sz-1 ); } else {dp[i][c1]=min(dp[i][c1],dp[i-1][c2]+sz );}}}int ans=0x3f3f3f3f;for ( int i=0; i<G[n].size(); i++ ) ans=min(ans, dp[n][G[n][i]]);printf("%d\n", ans);}return 0;
}