BZOJ 3128.「USACO 2013 · Open」Figure Eight

这谁想得到是 DP 呀……
可以考虑分别算上下矩形然后再合并。

显然,我们要基于上矩形的下边界和下矩形的上边界来计算。
fi,l,rf_{i,l,r} 表示当矩形的边界为 (i,l)(i,r)(i,l) \sim (i,r) 时,能得到的最大合法高度。
注意此时并不需要判断下边界上是否有障碍,原因等会再说。

有一个显然的 O(n4)O(n^4) 转移即枚举 i,l,ri,l,r 和高度,并且用行和列的前缀和来判定。
然鹅这样灰常傻……
为什么我们要留下边界不判呢?就是为了转移时直接沿用 fi1,l,rf_{i - 1,l,r} 的答案。
于是就可以做到 O(n3)O(n^3) 了。

然后设 gi,l,rg_{i,l,r} 表示矩形的边界对应的最大高度,转移类似。

考虑合并。
hi,l,rh_{i,l,r} 表示当矩形的边界为 (i,l)(i,r)(i,l) \sim (i,r) 时,矩形的最大面积。
借助 f,gf,g 有一个更傻的 O(n5)O(n^5) 的转移……

注意到这个转移的过程相当于找 max[l,r][l,r](rl1)(fi,l,r2)\max\limits_{[l',r'] \subseteq [l,r]}(r' - l' - 1)(f_{i,l',r' - 2)}
那么我们可以考虑合并 hi,l+1,rh_{i,l + 1,r}hi,l,r1h_{i,l,r - 1} 的值为 hi,l,rh_{i,l,r},并且加入 fi,l,rf_{i,l,r} 的贡献。
显然对于 [l,r][l,r][l',r'] \subset [l,r] 必有 [l,r][l+1,r][l',r'] \subseteq [l + 1,r][l,r][l,r1][l',r'] \subseteq [l,r - 1](注意是真子集)。

然后会发现空间炸了。这就是我设 f,gf,g 为高度而非面积的原因:开成 short 即可。
注意 hh 转移时和 ii 无关,所以可以压掉 ii 这一维。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
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);
}