P1950 长方形
看完题解有所启发的一个另解。
考虑对于每一行，底边在这一行上的方案数。然后考虑枚举高度 \(h\)。底边可以取的范围可以抽象成若干个连续段，底边只能在这几个连续段中取。那么考虑先递推求出一个点可以往上延申多少格，然后从 \(n\) 到 \(1\) 枚举高度 \(h\)，维护连续段以及加入延申格式恰好为 \(h\) 的点。可以动态加点的过程中合并连续段，并且更新方案数。最后的答案即对于所有 \(h\) 的方案数之和。
#include <iostream>
#include <vector>
using ll = long long;
int r[1007], l[1007];
ll ans;
ll f(int L, int R) { return ll(R - L + 2) * (R - L + 1) / 2; }
void merge(int x) {
if (l[x] == 0 || r[x + 1] == 0) return;
ans -= f(l[x], x);
ans -= f(x + 1, r[x + 1]);
ans += f(l[x], r[x + 1]);
r[l[x]] = r[x + 1], l[r[x + 1]] = l[x];
l[x] = r[x + 1] = 0;
}
void add(int x) {
l[x] = r[x] = x, ++ans;
merge(x - 1), merge(x);
}
int n, m;
int h[1007];
std::vector<int> v[1007];
ll solve() {
ans = 0;
for (int i = 0; i <= n; ++i) std::vector<int>().swap(v[i]);
for (int i = 1; i <= m; ++i) {
v[h[i]].push_back(i);
l[i] = r[i] = 0;
}
ll res = 0;
for (int i = n; i >= 1; --i) {
for (auto j : v[i]) add(j);
res += ans;
}
return res;
}
int main() {
std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);
std::cin >> n >> m;
ll res = 0;
for (int i = 1; i <= n; ++i) {
std::string s;
std::cin >> s;
for (int j = 1; j <= m; ++j) {
if (s[j - 1] == '.') {
++h[j];
} else {
h[j] = 0;
}
}
res += solve();
}
std::cout << res << '\n';
return 0;
}
同样地，这个技巧也可以运用在 P4147 玉蟾宫 上。
#include <iostream>
#include <vector>
using ll = long long;
int r[1007], l[1007];
ll ans;
ll f(int L, int R) { return R - L + 1; }
void merge(int x) {
if (l[x] == 0 || r[x + 1] == 0) return;
ans = std::max(ans, f(l[x], r[x + 1]));
r[l[x]] = r[x + 1], l[r[x + 1]] = l[x];
l[x] = r[x + 1] = 0;
}
void add(int x) {
l[x] = r[x] = x, ans = std::max(ans, 1ll);
merge(x - 1), merge(x);
}
int n, m;
int h[1007];
std::vector<int> v[1007];
ll solve() {
ans = 0;
for (int i = 0; i <= n; ++i) std::vector<int>().swap(v[i]);
for (int i = 1; i <= m; ++i) {
v[h[i]].push_back(i);
l[i] = r[i] = 0;
}
ll res = 0;
for (int i = n; i >= 1; --i) {
for (auto j : v[i]) add(j);
res = std::max(res, ans * i);
}
return res;
}
int main() {
std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);
std::cin >> n >> m;
ll res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char c;
std::cin >> c;
if (c == 'F') {
++h[j];
} else {
h[j] = 0;
}
}
res = std::max(res, solve());
}
std::cout << res * 3 << '\n';
return 0;
}