BZOJ 3128 「USACO 2013 · Open」Figure Eight

发表于 | 分类于 | 8

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

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

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

然后设 gi,l,r 表示下矩形的上边界对应的最大高度，转移类似。

考虑合并。
设 hi,l,r 表示当下矩形的上边界为 (i,l)∼(i,r) 时，上矩形的最大面积。
借助 f,g 有一个更傻的 O(n5) 的转移……

注意到这个转移的过程相当于找 max[l′,r′]⊆[l,r](r′−l′−1)(fi,l′,r′−2)。
那么我们可以考虑合并 hi,l+1,r 和 hi,l,r−1 的值为 hi,l,r，并且加入 fi,l,r 的贡献。
显然对于 [l′,r′]⊂[l,r] 必有 [l′,r′]⊆[l+1,r] 或 [l′,r′]⊆[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
#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);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment