uva 11552 - Fewest Flops(dp)

제목 링크: uva 11552 - Fewest Flops
제목 대의: k와 문자열을 정하고 문자열의 길이는 k의 배수로 문자열을len/k부로 나눈다. 한 부의 알파벳은 임의로 위치를 바꿀 수 있다. 현재 한 부의 알파벳을 다시 배열한 후에 알파벳의 블록 수가 가장 작다.
문제풀이 사고방식: dp[i][j]는 i/k부에서 j 문자로 끝나는 자모 블록수를 나타낸다.

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 1005;
const int M = 30;
const int INF = 0x3f3f3f3f;

int n, k, v[N][M], dp[N][M], c[N];

void init () {
	char str[N];
	memset(c, 0, sizeof(c));
	memset(v, 0, sizeof(v));
	memset(dp, INF, sizeof(dp));

	scanf("%d%s", &k, str);		
	n = strlen(str);
	for (int i = 0; i < n; i += k) {
		for (int j = 0; j < k; j++) {
			int u = str[j+i] - 'a';
			if (v[i][u] == 0) c[i]++;
			v[i][u]++;
		}
	}
}

int solve () {
	if (n == k) return c[0];

	int ans = INF;
	for (int i = 0; i < 26; i++) if (v[0][i]) dp[0][i] = c[0];

	for (int i = k; i < n; i += k) {
		for (int j = 0; j < 26; j++) if (v[i-k][j]) {

			for (int t = 0; t < 26; t++) {
				if (!v[i][t]) continue;
				if (v[i][j] && (j != t || c[i] == 1)) {
					dp[i][t] = min(dp[i][t], dp[i-k][j]+c[i]-1);
				} else 
					dp[i][t] = min(dp[i][t], dp[i-k][j]+c[i]);
				if (n == i + k)
					ans = min(dp[i][t], ans);
			}
		}
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		printf("%d
", solve());
	}
	return 0;
}