消除字符串
题目大意：在小A手里有一个字符串 \(S\)，小A每次都会进行这样的操作：从 \(S\) 中挑选一个回文的子序列，将其从字符串\(S\)中去除，剩下的字符重组成新的字符串\(S\)。
小A想知道，最少可以进行多少次操作，可以消除整个字符串。
解法：很显然的状压DP，每次看看是不是回文串就行了。
AC代码：
#include#include #include #include const int MAXN = 16;const int INF = 0x3f3f3f3f;using namespace std;char s[MAXN + 5];char tmp[MAXN + 5];int l;void init() { scanf("%s", s); l = strlen(s);}bool isPalindrome(bitset < 20 > S) { int tot = 0; for (int i = 0; i < l; ++i) if (S[i]) tmp[tot++] = s[i]; int left = 0, right = tot - 1; while (left < right) { if (tmp[left] != tmp[right]) return false; ++left; --right; } return true;}int dp[50000 + 5];int main() { init(); for (int i = 1; i < (1 << l); ++i) { bitset < 20 > S; S = i; dp[i] = isPalindrome(S) ? 1 : INF; for (int j = i; j; j = (j - 1) & i) dp[i] = min(dp[i], dp[j] + dp[i ^ j]); } printf("%d\n", dp[(1 << l) - 1]); return 0;}
BZOJ1087 [SCOI2005]互不侵犯King
很水的状压DP，预处理一波就好了。
#include#include #include #include typedef long long LL;const int MAXN = 10;using namespace std;inline int read() { int x = 0, w = 1; char c = ' '; while (c < '0' || c > '9') { c = getchar(); if (c == '-') w = -1; } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * w;}int n, m;LL dp[MAXN + 5][MAXN * MAXN + 5][1 << MAXN], cnt[1 << MAXN];bool isBanned[1 << MAXN], conflict[1 << MAXN][1 << MAXN]; bitset < 10 > S;void init() { n = read(); m = read(); memset(isBanned, true, sizeof(isBanned)); memset(conflict, true, sizeof(conflict)); for (int i = 0; i < (1 << n); ++i) if (!(i & (i << 1))) { S = i; cnt[i] = S.count(); isBanned[i] = false; } for (int i = 0; i < (1 << n); ++i) if (!isBanned[i]) for (int j = 0; j < (1 << n); ++j) if (!isBanned[j]) if (!(i & j) && !((i << 1) & j) && !((i >> 1) & j)) conflict[i][j] = false;}int main() { init(); for (int i = 0; i < (1 << n); ++i) if (!isBanned[i]) dp[1][cnt[i]][i] = 1; for (int i = 2; i <= n; ++i) for (int j = 0; j < (1 << n); ++j) if (!isBanned[j]) for (int k = 0; k < (1 << n); ++k) if (!isBanned[k] && !conflict[j][k]) for (int num = cnt[j]; num + cnt[k] <= m; ++num) dp[i][num + cnt[k]][k] += dp[i - 1][num][j]; LL ans = 0; for (int i = 0; i < (1 << n); ++i) ans += dp[n][m][i]; printf("%lld", ans); return 0;}
洛谷P2704 [NOI2001]炮兵阵地
和上一题差不多，可是我调不对啊。
记一下上一行的状态就行了。
#include#include #include #include #define max(a, b) (a < b ? b : a)const int MAXN = 100;const int MAXM = 10;using namespace std;inline int read() { int x = 0, w = 1; char c = ' '; while (c < '0' || c > '9') { c = getchar(); if (c == '-') w = -1; } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * w;}int n, m, cnt[1 << MAXM], dp[3][1 << MAXM][1 << MAXM], cantPlace[MAXN + 5];bool isBanned[1 << MAXM];bitset < 10 > S;void init() { n = read(); m = read(); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { char c = getchar(); while (c != 'H' && c != 'P') c = getchar(); cantPlace[i] *= 2; cantPlace[i] += c == 'H'; } memset(isBanned, true, sizeof(isBanned)); for (int i = 0; i < (1 << m); ++i) if (!(i & (i << 2)) && !(i & (i << 1))) { S = i; cnt[i] = S.count(); isBanned[i] = false; } for (int i = 1; i <= n; ++i) for (int j = 0; j < (1 << m); ++j) if (!isBanned[j] && !(cantPlace[i] & j)) for (int k = 0; k < (1 << m); ++k) if (!isBanned[k] && !(j & k) && !(cantPlace[i - 1] & k)) dp[i % 2][j][k] = max(dp[i % 2][j][k], cnt[j]);}int main() { init(); for (int i = 2; i <= n; ++i) for (int j = 0; j < (1 << m); ++j) if (!isBanned[j] && !(cantPlace[i] & j)) for (int k = 0; k < (1 << m); ++k) if (!isBanned[k] && !(j & k) && !(cantPlace[i - 1] & k)) for (int last = 0; last < (1 << m); ++last) if (!isBanned[last] && !(k & last) && !(cantPlace[i - 2] & last) && !(j & last)) dp[i % 2][j][k] = max(dp[i % 2][j][k], dp[(i - 1) % 2][k][last] + cnt[j]); int ans = 0; for (int i = 0; i < (1 << m); ++i) if (!isBanned[i] && !(cantPlace[n] & i)) for (int j = 0; j < (1 << m); ++j) if (!isBanned[j] && !(cantPlace[n - 1] & j) && !(i & j)) ans = max(ans, dp[n % 2][i][j]); printf("%d\n", ans); return 0;}
总结
其实状压DP都比较显然，在dp需要集合状态时，我们就可以考虑状压DP。
学会bitset也能使你的状压DP代码复杂度和时间复杂度更低（卡常神器）? 最主要还是多练，预处理好像一般都是套路。