Rockdu's Blog

这道题的DP其实可以换一个角度出发思考，因为我们可以随意调整一个块，所以每一个块有字母的种类个数肯定是该块的最优块数。接下来我们只需要确定它们的排布就可以了。我们这样建立状态。dp[i][j]表示第i个块的第一个字母为j时的最少联通个数，这样我们就可以通过dp[i - 1][0~25]推出dp[i][0 ~25]了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e3 + 5;
int dp[maxn][26];
bool idx[maxn][26];
int num[maxn];
char s[maxn];

int main() {
	int t, k; scanf("%d", &t);
	while(t--) {
		scanf("%d", &k);
		scanf("%s", s);
		memset(dp, 0x3f, sizeof(dp));
		int len = strlen(s);
		for(register int i = 0; i < len; ++i) 
			num[i / k] += !(idx[i / k][s[i] - 'a']), idx[i / k][s[i] - 'a'] = 1;
		for(register int i = 0; i < 26; ++i) 
			if(idx[0][i]) dp[0][i] = num[0];
		for(register int i = 1; i < len / k; ++i) 
			for(register int j = 0; j < 26; ++j) {
				if(dp[i - 1][j])
					for(register int k = 0; k < 26; ++k)
						if(idx[i][k] && (k != j || num[i - 1] == 1))
							dp[i][k] = min(dp[i - 1][j] + num[i] - (idx[i - 1][k] != 0), dp[i][k]);
			}
		int mn = 0x3f3f3f3f;
		for(register int i = 0; i < 26; ++i)
			if(dp[len / k - 1][i])
				mn = min(dp[len / k - 1][i], mn);
		printf("%d\n", mn);
		memset(idx, 0, sizeof(idx));
		memset(num, 0, sizeof(num));
	}
	return 0;
}