题目描述
给定一个 $n\times n$ 的棋盘，有一些格子要求一定是黑色，其它可以染白或染黑，定义棋盘的优美度为最大连续白色正方形的变成，对于 $i\in[0,n]$， 求有多少种染色方案使得棋盘的优美度为 $i$
$n\le 8$
Solution
我们考虑最大白色正方形的 $dp$，显然是这个东西 $f[i][j]=min\lbrace f[i-1][j],f[i][j-1],f[i-1][j-1]\rbrace+1$，其中 $(i,j)$ 为白色
按照套路，我们需要把这个东西压进状态，这里我们不能直接压一行，而是需要压一条长度为 $n+1$ 的轮廓线
根据暴力计算能够得到最多只有几万个状态，所以扔到 $map$ 里也没问题，注意我还需要在 $dp$ 状态里记录历史最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#define maxn 9
using namespace std;
const int p = 1000000007;
int n, m, a[maxn];
char s[maxn];
map<vector<int>, int> f[maxn][maxn][maxn];
int ans[maxn];
void work() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s + 1; a[i] = 0;
for (int j = 1; j <= n; ++j)
if (s[j] == 'o') a[i] |= 1 << j - 1;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 0; k <= n; ++k) f[i][j][k].clear();
vector<int> tmp(n + 1); f[1][1][0][tmp] = 1;
if (a[1] & 1) tmp[0] = 1, f[1][1][1][tmp] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < n; ++j)
for (int k = 0; k <= n; ++k)
for (auto [s, v] : f[i][j][k]) {
vector<int> t(n + 1);
for (int o = 0; o < j; ++o) t[o] = s[o];
for (int o = j + 1; o <= n; ++o) t[o] = s[o];
if (a[i] >> j & 1) {
t[j] = min({ s[j - 1], s[j], s[j + 1] }) + 1;
f[i][j + 1][max(t[j], k)][t] = (f[i][j + 1][max(t[j], k)][t] + v) % p;
} t[j] = 0;
f[i][j + 1][k][t] = (f[i][j + 1][k][t] + v) % p;
}
if (i < n)
for (int k = 0; k <= n; ++k)
for (auto [s, v] : f[i][n][k]) {
vector<int> t(n + 1);
for (int o = 1; o <= n; ++o) t[o] = s[o - 1];
if (a[i + 1] & 1) {
t[0] = 1;
f[i + 1][1][max(t[0], k)][t] = (f[i + 1][1][max(t[0], k)][t] + v) % p;
} t[0] = 0;
f[i + 1][1][k][t] = (f[i + 1][1][k][t] + v) % p;
}
}
fill(ans, ans + maxn, 0);
for (int k = 0; k <= n; ++k)
for (auto [vec, val] : f[n][n][k]) ans[k] = (ans[k] + val) % p;
for (int i = 0; i <= n; ++i) cout << ans[i] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|