这谁想得到是 DP 呀……
可以考虑分别算上下矩形然后再合并。
显然，我们要基于上矩形的下边界和下矩形的上边界来计算。
设 \(f_{i,l,r}\) 表示当上矩形的下边界为 \((i,l) \sim (i,r)\) 时，能得到的最大合法高度。
注意此时并不需要判断下边界上是否有障碍，原因等会再说。
有一个显然的 \(O(n^4)\) 转移即枚举 \(i,l,r\) 和高度，并且用行和列的前缀和来判定。
然鹅这样灰常傻……
为什么我们要留下边界不判呢？就是为了转移时直接沿用 \(f_{i - 1,l,r}\) 的答案。
于是就可以做到 \(O(n^3)\) 了。
然后设 \(g_{i,l,r}\) 表示下矩形的上边界对应的最大高度，转移类似。
考虑合并。
设 \(h_{i,l,r}\) 表示当下矩形的上边界为 \((i,l) \sim (i,r)\) 时，上矩形的最大面积。
借助 \(f,g\) 有一个更傻的 \(O(n^5)\) 的转移……
注意到这个转移的过程相当于找 \(\max\limits_{[l',r'] \subseteq [l,r]}(r' - l' - 1)(f_{i,l',r' - 2)}\)。
那么我们可以考虑合并 \(h_{i,l + 1,r}\) 和 \(h_{i,l,r - 1}\) 的值为 \(h_{i,l,r}\)，并且加入 \(f_{i,l,r}\) 的贡献。
显然对于 \([l',r'] \subset [l,r]\) 必有 \([l',r'] \subseteq [l + 1,r]\) 或 \([l',r'] \subseteq [l,r - 1]\)（注意是真子集）。
然后会发现空间炸了。这就是我设 \(f,g\) 为高度而非面积的原因：开成 short 即可。
注意 \(h\) 转移时和 \(i\) 无关，所以可以压掉 \(i\) 这一维。
代码： 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
using namespace std;
const int N = 300;
int n;
char a[N + 5][N + 5];
short sum[2][N + 5][N + 5];
short f[N + 5][N + 5][N + 5],g[N + 5][N + 5][N + 5];
int h[N + 5][N + 5];
int ans;
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= n;++j)
{
scanf(" %c",a[i] + j),a[i][j] = a[i][j] == '*';
sum[0][i][j] = sum[0][i][j - 1] + a[i][j];
sum[1][j][i] = sum[1][j][i - 1] + a[i][j];
}
for(register int l = 1;l <= n - 2;++l)
for(register int r = l + 2;r <= n;++r)
for(register int i = 3;i <= n;++i)
{
int len = f[i - 1][l][r] + 3;
if(!f[i - 1][l][r])
len = 0;
if(!(sum[0][i - 2][r] - sum[0][i - 2][l - 1]))
f[i][l][r] = max(f[i][l][r],(short)1);
if(!(sum[1][l][i] - sum[1][l][i - len])
&& !(sum[1][r][i] - sum[1][r][i - len]))
f[i][l][r] = max(f[i][l][r],(short)(len - 2));
}
for(register int l = 1;l <= n - 2;++l)
for(register int r = l + 2;r <= n;++r)
for(register int i = n - 2;i;--i)
{
int len = g[i + 1][l][r] + 3;
if(!g[i + 1][l][r])
len = 0;
if(!(sum[0][i + 2][r] - sum[0][i + 2][l - 1]))
g[i][l][r] = max(g[i][l][r],(short)1);
if(!(sum[1][l][i + len - 1] - sum[1][l][i - 1])
&& !(sum[1][r][i + len - 1] - sum[1][r][i - 1]))
g[i][l][r] = max(g[i][l][r],(short)(len - 2));
}
for(register int i = 3;i <= n - 2;++i)
{
memset(h,0,sizeof h);
for(register int len = 3;len <= n;++len)
for(register int l = 1,r = len;r <= n;++l,++r)
if(!(sum[0][i][r] - sum[0][i][l - 1]))
ans = max(ans,(h[l][r] = max(max(h[l + 1][r],h[l][r - 1]),f[i][l][r] * (r - l - 1))) * g[i][l][r] * (r - l - 1));
}
if(!ans)
puts("-1");
else
printf("%d\n",ans);
}