Codeforces 903F Clear The Matrix(状态压缩DP)

题目链接 Clear The Matrix

题意 给定一个$4 * n$的矩形,里面的元素为$'.'$或$'*'$。现在有$4$种正方形可以覆盖掉$'*'$,正方形的边长分别为$1,2,3,4$。

求把整个矩形变成全$'.'$的最小代价。

考虑状压DP

设$f[i][j]$为前$i$列已经全部变成'.',第$i + 1$到第$i + 4$列的这$16$个格子状态为$j$的最小花费。

这$16$个格子标号如下

$0$   $4$   $8$   $12$

$1$   $5$   $9$   $13$

$2$   $6$  $10$  $14$

$3$   $7$  $11$  $15$

我们可以枚举$0,1,2,3$这$4$个格子。以当前格子为左上角的正方形的边长。

其中$0$号格子可以放边长为$0, 1, 2, 3, 4$的正方形;

$1$号格子可以放边长为$0, 1, 2, 3$的正方形;

$2$号格子可以放边长为$0, 1, 2$的正方形;

$3$号格子可以放边长为$0, 1$的正方形;

放边长为$0$的正方形等效为不放。

当枚举的这些正方形可以完全盖住$0,1,2,3$这$4$个格子的时候,就可以进行状态转移。

状态稍微有点复杂,用二进制位表示……

时间复杂度$O(n * 2^{16} * 5!)$

Codeforces 903F Clear The Matrix(状态压缩DP)

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 1e3 + 10;
const int S = 1 << 16; char s[N];
int f[N][S + 2];
int a[6][N];
int c[10];
int g[10];
int n;
int pre[N];
int ans;
int cnt, mask; void up(int &a, int b){ if (a > b) a = b;}
inline get(int x){ return x ^ (S - 1);} int main(){ scanf("%d", &n);
rep(i, 1, 4) scanf("%d", c + i); rep(i, 1, 4){
scanf("%s", s + 1);
rep(j, 1, n) a[i][j] = s[j] == '*';
} rep(k, 0, n){
rep(i, 0, S + 1) f[k][i] = 1e9;
} cnt = -1;
mask = 0;
rep(i, 1, 4){
rep(j, 1, 4){
++cnt;
if (a[j][i]) mask |= (1 << cnt);
}
}
f[0][mask] = 0; g[0] = 0;
g[1] = 1;
g[2] = (1 << 0) ^ (1 << 1) ^ (1 << 4) ^ (1 << 5);
g[3] = (1 << 0) ^ (1 << 1) ^ (1 << 2);
g[3] ^= ((1 << 4) ^ (1 << 5) ^ (1 << 6));
g[3] ^= ((1 << 8) ^ (1 << 9) ^ (1 << 10));
g[4] = (1 << 16) - 1; rep(k, 0, n){
int extra = 0;
rep(j, 1, 4) if (a[j][k + 5]) extra |= (1 << (j + 11)); rep(j, 0, S - 1){
if (f[k][j] >= 1e9) continue;
rep(aa, 0, 4){
rep(bb, 0, 3){
rep(cc, 0, 2){
rep(dd, 0, 1){
int cnt = get(g[aa]) & get(g[bb] << 1) & get(g[cc] << 2) & get(g[dd] << 3);
if ((cnt & j & 15) == 0){
int nowmask = cnt & j;
nowmask >>= 4;
nowmask ^= extra;
up(f[k + 1][nowmask], f[k][j] + c[aa] + c[bb] + c[cc] + c[dd]);
}
}
}
}
}
}
} ans = 1e9;
rep(i, n - 4, n) ans = min(ans, f[i][0]);
printf("%d\n", ans);
return 0;
}

 

我们可以考虑使用滚动数组,于是空间大大节省

Codeforces 903F Clear The Matrix(状态压缩DP)

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL; const int N = 1e3 + 10;
const int S = 1 << 16; char s[N];
int f[2][S + 2];
int a[6][N];
int c[10];
int g[10];
int n;
int pre;
int ans;
int cnt, mask; void up(int &a, int b){ if (a > b) a = b;}
inline get(int x){ return x ^ (S - 1);} int main(){ scanf("%d", &n);
rep(i, 1, 4) scanf("%d", c + i); rep(i, 1, 4){
scanf("%s", s + 1);
rep(j, 1, n) a[i][j] = s[j] == '*';
} rep(k, 0, 1) rep(i, 0, S + 1) f[k][i] = 1e9; cnt = -1;
mask = 0;
rep(i, 1, 4){
rep(j, 1, 4){
++cnt;
if (a[j][i]) mask |= (1 << cnt);
}
}
f[0][mask] = 0;
pre = 0; g[0] = 0;
g[1] = 1;
g[2] = (1 << 0) ^ (1 << 1) ^ (1 << 4) ^ (1 << 5);
g[3] = (1 << 0) ^ (1 << 1) ^ (1 << 2);
g[3] ^= ((1 << 4) ^ (1 << 5) ^ (1 << 6));
g[3] ^= ((1 << 8) ^ (1 << 9) ^ (1 << 10));
g[4] = (1 << 16) - 1; rep(i, 0, n){
int extra = 0;
rep(j, 1, 4) if (a[j][i + 5]) extra |= (1 << (j + 11)); rep(j, 0, S + 1) f[pre ^ 1][j] = 1e9; rep(j, 0, S - 1){
if (f[pre][j] >= 1e9) continue;
rep(aa, 0, 4){
rep(bb, 0, 3){
rep(cc, 0, 2){
rep(dd, 0, 1){
int cnt = get(g[aa]) & get(g[bb] << 1) & get(g[cc] << 2) & get(g[dd] << 3);
if ((cnt & j & 15) == 0){
int nowmask = cnt & j;
nowmask >>= 4;
nowmask ^= extra;
up(f[pre ^ 1][nowmask], f[pre][j] + c[aa] + c[bb] + c[cc] + c[dd]);
}
}
}
}
}
}
pre ^= 1;
} printf("%d\n", f[pre][0]);
return 0;
}

不过这个做法还不是最优的= =

官方题解给出的做法是只存后面12个格子的状态的

因为当考虑某一列的时候一旦用到$4*4$的正方形,其他边长的正方形就不用再考虑了……直接无视掉。

这样的话可以直接从$f[k][nowmask]$转移到$f[k + 1][0]$

时间复杂度$O(n * 2^{12} * 96)$

Codeforces 903F Clear The Matrix(状态压缩DP)

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 1e3 + 10;
const int S = 1 << 12; char s[N];
int f[2][S + 2], a[6][N], c[10], g[10];
int n, x, cnt, mask, ans; void up(int &a, int b){ if (a > b) a = b;}
inline get(int x){ return x ^ (S - 1);} int main(){ scanf("%d", &n);
rep(i, 1, 4) scanf("%d", c + i); rep(i, 1, 4){
scanf("%s", s + 1);
rep(j, 1, n) a[i][j] = s[j] == '*';
} rep(k, 0, 1) rep(i, 0, S + 1) f[k][i] = 1e9; cnt = -1;
mask = 0; rep(i, 1, 3){ rep(j, 1, 4){ ++cnt; if (a[j][i]) mask |= (1 << cnt); }} f[0][mask] = 0;
x = 0; g[0] = 0;
g[1] = 1;
g[2] = 51;
g[3] = 1911; rep(i, 0, n){
int extra = 0;
rep(j, 1, 4) if (a[j][i + 4]) extra |= (1 << (j + 7));
rep(j, 0, S + 1) f[x ^ 1][j] = 1e9; rep(j, 0, S - 1){
if (f[x][j] >= 1e9) continue;
rep(aa, 0, 3){
rep(bb, 0, 3){
rep(cc, 0, 2){
rep(dd, 0, 1){
int cnt = get(g[aa]) & get(g[bb] << 1) & get(g[cc] << 2) & get(g[dd] << 3);
if ((cnt & j & 15) == 0){
mask = (cnt & j) >> 4;
mask ^= extra;
up(f[x ^ 1][mask], f[x][j] + c[aa] + c[bb] + c[cc] + c[dd]);
}
}
}
}
}
up(f[x ^ 1][0], f[x][j] + c[4]);
}
x ^= 1;
} printf("%d\n", f[x][0]);
return 0;
}
上一篇:常见排序算法题(java版)


下一篇:Clear The Matrix CodeForces - 903F (状压)