题意：

一个由大写字母组成的长度为\(n(n \leq 75)\)的字符串，每次操作可以交换相邻位置的两个字母，求最少操作多少次使字符串中不出现子串VK

分析：

VK之外的字母具体是什么，我们并不关心，所以可以统一设它们为X

设\(d(v,k,x,t)\)表示，已经确定前\(v\)个V，前\(k\)个K和前\(x\)个X为字符串的前\(v+k+x\)个字母，\(t\)取\(0\)或\(1\)表示第\(v+k+x\)个字母是否为V，最少需要操作多少次

在转移的时候可以选择后面的第\(v+1\)个V或第\(k+1\)个K或第\(x+1\)个X接在后面

注意如果此时\(t=1\)，也就是最后一个字母为V，那么就不能选择K

因为操作都是两两相邻交换，所以未确定位置的字母相对顺序不会变

要将位置为\(pos\)确定为第\(v+k+x+1\)个字母时，费用为位置在\(pos\)之前且未确定的字母的个数，这些可以\(O(n)\)统计或预处理前缀和\(O(1)\)计算

所以最终时间复杂度为\(O(n^4)\)或\(O(n^3)\)

#include <cstdio>

#include <cstring>

const int maxn = 76;

const int INF = 0x3f3f3f3f;

int n;

char s[maxn];

int d[maxn][maxn][maxn][2];

int pos[3][maxn], cnt[3], used[3]; // V, K, X

void upd(int& a, int b) { if(b < a) a = b; }

int cost(int limit) {

	int ans = 0;

	for(int i = 0; i < 3; i++) {

		for(int j = used[i] + 1; j <= cnt[i] && pos[i][j] < limit; j++)

			ans++;

	}

	return ans;

}

int main()

{

	scanf("%d\n%s", &n, s);

	for(int i = 0; i < n; i++) {

		if(s[i] == 'V') pos[0][++cnt[0]] = i;

		else if(s[i] == 'K') pos[1][++cnt[1]] = i;

		else pos[2][++cnt[2]] = i;

	}

	memset(d, 0x3f, sizeof(d));

	d[0][0][0][0] = 0;

	int tot = 0;

	int &v = used[0], &k = used[1], &x = used[2];

	for(v = 0; v <= cnt[0]; v++) {

		for(k = 0; k <= cnt[1]; k++) {

			for(x = 0; x <= cnt[2]; x++) {

				for(int t = 0; t <= 1; t++) {

					int& cur = d[v][k][x][t];

					if(cur == INF) continue;

					if(v < cnt[0]) upd(d[v+1][k][x][1], cur+cost(pos[0][v+1]));

					if(k < cnt[1] && t == 0) upd(d[v][k+1][x][0], cur+cost(pos[1][k+1]));

					if(x < cnt[2]) upd(d[v][k][x+1][0], cur+cost(pos[2][x+1]));

				}

			}

		}

	}

	int ans = INF;

	for(int t = 0; t < 2; t++) upd(ans, d[cnt[0]][cnt[1]][cnt[2]][t]);

	printf("%d\n", ans);

	return 0;

}

巴特西

Codeforces 771E Bear and Rectangle Strips DP

题意：

分析：

最新文章

热门文章