状态压缩DP 三题 POJ2441 POJ3254 POJ2836
最近比较闲, 然后玩Minecraft玩的天昏地暗. 在这危急存亡之秋(果然是秋天), 畅神苦口婆心鼓励我多刷题少挖矿, 尤其要多刷状压DP. 于是今天搞个状压专题. 此外, 最近<爬虫>系列文章一直不更新, 是由于畅神教导我, 要多刷题少撸站. 所以我还是等风头过去了, 再更新系列文章吧.
POJ 2441 Arrange the Bulls
FJ的公牛们喜欢打篮球, 但是这些牛都觉得别的牛太弱, 不想和别的牛一起玩. FJ有N头牛, M个谷仓(篮球场). 这些牛非常挑剔, 只在某些自己喜欢的谷仓里打篮球, 而且不愿和别的牛分享同一个场地.
求符合牛们要求的分配场地的方案总数(不会超过1e7).
1 <= N <= 20
1 <= M <= 20
设dp[i][j] 大小为 dp[20][1 << 20], 表示已经考虑完1~(i-1)号牛的前提下, 考虑前i头牛(包括i)在状态j下的方案数. 如果i头牛喜欢y号球场, 那么如果状态j的y号球场是空着的, 有dp[i][j | 1 << y] += dp[i][j].
按顺序处理所有状态即可. 但是dp[20][1 << 20] 这个大小会MLE, 用滚动数组dp[2][ 1 << 20]即可. 下面代码第二层for循环的if (dp[(i-1)&1][j])这一句是因为为了滚动数组, 后面对dp[上一头牛][球场状态] 进行清空而写的. 否则会得到诡异的结果.
/**
* I love coding
* @Author: Jecvay
*/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "
inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////
#define inf 0x4F4F4F4F
const int maxn = 20 + 10;
int n, m;
bool like[maxn][maxn];
int dp[2][1 << 20];
/////////////////
void solve() {
dp[0][0] = 1;
for (int i = 1; i <= n; i++) { // 牛i
for (int j = 0; j < (1 << m); j++) if (dp[(i-1)&1][j]) { // 球场状态
for (int k = 1; k <= m; k++) { // 牛i喜欢的球场
if (like[i][k] && j != (j | (1 << (k-1)))) {
dp[i&1][j | (1<<(k-1))] += dp[(i-1)&1][j];
}
}
}
memset(dp[(i-1)&1], 0, sizeof(dp[(i-1)&1]));
}
int ans = 0;
for (int i = 0; i < (1 << m); i++) {
ans += dp[n&1][i];
}
cout << ans << endl;
}
int main() {
n = gint();
m = gint();
for (int i = 1; i <= n; i++) {
int x = gint();
for (int j = 0; j < x; j++) {
int l = gint();
like[i][l] = true;
}
}
solve();
return 0;
}
POJ 3254 Corn Fields
FJ 买了一块 M * N 的草地, 在上面种草给牛吃. 他不在相邻的两个格子里都种, 因为牛们不喜欢吃饭的时候太靠近别牛. 而且有的格子因为不肥沃还种不了.
请你算出有多少种种草的方案(一个格子都不种也算一种方案).
1 <= M <= 12
1 <= N <= 12
设dp[i][j]大小为dp[12][1 << 12], 表示当考虑到第i行的时候种草状态为j时的方案数. 现在讨论 dp[i-1][k] 和 dp[i][j] 的关系:
- k和j都满足两个条件: (k << 1) & k == 0 而且 k 满足草地肥沃的限制 (j也是一样)
- k & j == 0
在上述条件满足的情况下, 可以有
dp[i][j] += dp[i-1][k]
对每个j, 遍历k, 即可. 代码如下:
/**
* I love coding
* @Author: Jecvay
*/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "
inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////
#define inf 0x4F4F4F4F
const int maxn = 12 + 10;
const int MOD = 1e8;
int n, m;
int can[maxn];
int dp[maxn][1 << maxn];
/////////////////
void solve() {
for (int i = 0; i < (1 << m); i++) {
if ((i << 1) & i) continue;
if ((i & can[1]) != i) continue;
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) { // 行
for (int j = 0; j < (1 << m); j++) { // 状态
if ((j << 1) & j)
continue;
if ((can[i] & j) != j)
continue;
for (int k = 0; k < (1 << m); k++) {
if ((k << 1) & k)
continue;
if ((can[i-1] & k) != k)
continue;
if (j & k)
continue;
dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
}
}
}
int ans = 0;
for (int i = 0; i < (1 << m); i++) {
ans += dp[n][i];
ans %= MOD;
}
cout << ans << endl;
}
int main() {
n = gint();
m = gint();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (gint())
can[i] += 1 << (j-1);
}
}
solve();
return 0;
}
/*
2 3
1 1 1
0 1 0
*/
POJ 2836 Rectangular Covering
给出笛卡尔坐标系下的 n 个点, 用边平行于坐标轴的数个长方形来覆盖这些所有的点. 一个点可以被覆盖多次, 每个长方形最少覆盖两个点(包括落在他的边上的点).
长方形的边长都是整数, 没有边长为0的特殊长方形存在. 没有坐标相同的点. 如何选择总面积最小的长方形来完成任务? 输出最小的总面积.
2 <= n <= 15
-1000 <= x, y <= 1000
这题坐标范围很大, 但是点的数量很少, 首先想到可以离散化. 一个 a * b 的长方形最多可以覆盖 (a+1) * (b+1) 个点. 但是这么想下去感觉没法做, 离散化后不好判断长方形的面积大小, 而且和状态压缩dp的思路不符.
然后看到这句话: 每个长方形最少覆盖两个点. 那么就可以每两个点形成一个长方形, 总共形成 n * (n-1) / 2 个长方形, 枚举这些长方形即可.
如果两个点构成的长方形是一条线段, 那么把面积算成线段的长度 * 1; 如果在两点形成的长方形之内还包含了其他点, 将这些点也算在这个长方形的状态之内.
所以这道题是先要进行比较麻烦的预处理, 然后才是状压DP.
预处理: 用 state[i] 来表示第 i 个长方形围住的点的集合, 用 squre[i] 来表示第 i 个长方形的面积.
DP: 设 S 是点集, dp[S] 表示围住这些点需要的最小总面积, 那么按照一个一个长方形加进去的顺序递推, 在 S 的基础上加入第 i 个长方形得到的点集是 T = S | state[i], dp[T] = min(dp[T], dp[S] + squre[i]) 就是转移方程了.
就是说, 旧矩形集, 加入一个长方形, 得到一个新矩形集, 那么 dp[新矩形集] 可以用 dp[旧矩形集] + 加入的长方形的面积 来更新. 代码如下:
/**
* I love coding
* @Author: Jecvay
*/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "
inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////
#define inf 0x4F4F4F4F
const int maxn = 15 + 10;
int n, m;
int x[maxn], y[maxn];
int state[maxn * maxn]; // 长方形 i 的点集
int squre[maxn * maxn]; // 长方形 i 的面积
int dp[1 << maxn];
/////////////////
void solve() {
/// 预处理
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) { // 点i 和 点j 构成的长方形.
state[cnt] = 0;
for (int k = 0; k < n; k++) { // 枚举所有点, 看是否在长方形内, 更新state[i]
if ((x[i] - x[k]) * (x[k] - x[j]) >= 0 &&
(y[i] - y[k]) * (y[k] - y[j]) >= 0) {
state[cnt] |= (1 << k);
}
}
if (x[i] == x[j]) squre[cnt] = abs(y[i] - y[j]);
else if (y[i] == y[j]) squre[cnt] = abs(x[i] - x[j]);
else squre[cnt] = abs((x[i]-x[j]) * (y[i]-y[j]));
cnt++;
}
}
/// DP
for (int s = 0; s < (1 << n); s++) {
dp[s] = inf;
}
dp[0] = 0;
for (int s = 0; s < (1 << n); s++) {
for (int i = 0; i < cnt; i++) {
int t = s | state[i];
if (t == s) // state[i] 是 s 的子集, 无需加入这个长方形i
continue;
dp[t] = min(dp[t], dp[s] + squre[i]);
}
}
cout << dp[(1 << n) - 1] << endl;
}
int main() {
while (~scanf("%d", &n) && n) {
for (int i = 0; i < n; i++) {
x[i] = gint();
y[i] = gint();
}
solve();
}
return 0;
}
/*
2
0 1
1 0
0
*/
关于玩物丧志以及健康破产
写到这里, 已经凌晨三点四十. 我觉得这对健康危害是很大的, 但是如果不写到现在, 就会觉得今天过得很空虚, 因为玩了一下午和一晚上的Minecraft, 说好的状压dp五道练习只做了1道. 于是从0点开始补了两道. 本来想补完4道, 但是觉得实在是对身体太不好, 只得作罢. 明天还要七点半起床抢火车票去打区域赛.
我觉得想要做一个充实的大学生是很蛋疼的事情. 首先各种电脑游戏很好玩, 其次外面很多东西很好吃, 很好玩, 在这种情况下, 每天都安排了学习任务, 学习了就不能吃喝玩乐了, 一旦迷恋上一款游戏, 比如Minecraft, 就会搞得好多计划都不能如期进行(比如爬虫系列文章没更新, 刷题变少, 计算机组成原理自学进度落后). 产生空虚的心理后, 还会造成晚上不想睡觉, 最后健康破产, 人生完蛋.
所以, 男人不能玩物丧志.
哈哈同学你好有趣