【BZOJ 2121】字符串游戏

http://www.lydsy.com/JudgeOnline/problem.php?id=2121

dp，设\(f(i,j,k,l)\)表示原串i到j这个子串能否被删成第k个串的长度为l的前缀。

再设\(can(i,j)\)表示原串i到j这个子串能否被删成空串，用can这个状态来加速f的转移即可。

时间复杂度\(O(|L|^3|S||p|)\)，区间dp的转移都很少，所以可以过。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int L = 160;

const int N = 43;

const int p = 33;

bool f[L][L][N][p], can[L][L];

int n, len[N], Slen, dp[L];

char s[N][p], S[L];

int main() {

	scanf("%s", S + 1);

	Slen = strlen(S + 1);

	scanf("%d", &n);

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

		scanf("%s", s[i] + 1);

		len[i] = strlen(s[i] + 1);

	}

	for (int i = Slen; i >= 1; --i)

		for (int j = i; j <= Slen; ++j) {

			for (int k = 1; k <= n; ++k) {

				f[i][i - 1][k][0] = true;

				for (int l = 1; l <= len[k] && l <= j - i + 1; ++l) {

					f[i][j][k][l] |= f[i][j - 1][k][l - 1] && (s[k][l] == S[j]);

					for (int tmp = i; tmp < j; ++tmp) f[i][j][k][l] |= f[i][tmp][k][l] && can[tmp + 1][j];

				}

			}

			for (int k = 1; k <= n; ++k)

				if (f[i][j][k][len[k]]) {

					can[i][j] = true;

					break;

				}

		}

	for (int i = 1; i <= Slen; ++i) {

		dp[i] = dp[i - 1] + 1;

		for (int j = i; j >= 1; --j)

			if (can[j][i])

				dp[i] = min(dp[i], dp[j - 1]);

	}

	printf("%d\n", dp[Slen]);

	return 0;

}

巴特西

【BZOJ 2121】字符串游戏

最新文章

热门文章