题解 P3135 【[USACO16JAN]堡哞Fort Moo】

· · 题解

200引导我们思考O(n^3)。

O(n^3)的矩阵中的dp最经典的不就是最大子矩阵了么？

让我们回忆一下最大子矩阵是怎么搞的。

两层循环枚举起始行和终止行，预处理每一列前缀和。
一层循环做dp：
如果仅选择当前列不比选择原结果优，暂时加入原结果。
如果仅选择当前列更优，舍弃原结果，选择当前列。
实时更新ans。

然后我们发现这玩意儿和最大子矩阵差不多。

两层循环枚举起始行和中止行，预处理列的连通性。
一层循环做dp:
如果这两行中间的某一列是连通的，说明它有成为一堵纵向墙的资格。
如果随着列的枚举，这两行的连通性被破坏(之间建不成横向墙)，那么前面的纵向墙就作废。
如果一堵纵向墙前面还有另一堵未被作废的纵向墙，那么可用来更新答案。

我知道看起来云里雾里的，所以放代码吧。

for(int i=1;i<=m;i++)
    {
        int x=0;
        for(int j=0;j<=n;j++)
         if(str[j][i]=='X'||!str[j][i]) x++;
         else a[j][i]=x;
    }

这一段是预处理纵向连通性的。如果一数列中数字一样且非0就连通，0是沼泽。

用样例打出来的a数组是这样的：

111111
110110
012012
212212
210212

对照一下代码应该很好理解吧。

for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
        for(int k=1;k<=m;k++)

枚举起始行中止行。扫过每一列。

if(str[i][k]!='.'||str[j][k]!='.') l=0;

l是较靠左的纵向墙。

如果地图中枚举出的这两行中有一片沼泽地的话，这片沼泽地的左侧的墙全都不能为这两行接下来的答案做出贡献了。所以左墙设为空。

if(a[i][k]==a[j][k]&&a[i][k])
{
        if(!l) l=k;
    else r=k,len=max(r-l+1,len);
}

如果满足a[i][k]==a[j][k]则纵向连通，但要排除a[i][k]==a[j][k]=0的情况（这样就是两片沼泽）。

这说明这儿有资格建纵向墙。

如果没有左侧的墙就赶紧把它设为左侧的墙。

我们是从左向右枚举的，我们自然希望较靠右的墙越靠右越好，所以如果左侧墙存在，我们可以直接把这列设为右侧墙，并且答案可更新。

最后乘一乘输出就好了。

完整代码奉上：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 210
using namespace std;
int n,m,a[N][N],f[N],ans;
char str[N][N];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
     scanf("%s",str[i]+1);
    for(int i=1;i<=m;i++)
    {
        int x=0;
        for(int j=0;j<=n;j++)
         if(str[j][i]=='X'||!str[j][i]) x++;
         else a[j][i]=x;
    }
    for(int i=1;i<n;i++)
     for(int j=i+1;j<=n;j++)
     {
        int len=0,l=0,r=0;
        memset(f,0,sizeof(f));
        for(int k=1;k<=m;k++)
        {
            if(str[i][k]!='.'||str[j][k]!='.') l=0;
            if(a[i][k]==a[j][k]&&a[i][k])
            {
                if(!l) l=k;
                else r=k,len=max(r-l+1,len);
            }
        }
        ans=max(ans,(j-i+1)*len);
     }
     printf("%d",ans);
     return 0;
}

后记：

这是我第一次不看题解（好吧，以前看过，不过我没记住题解内容，也算独立完成吧）写蓝题dp，我一直不擅长dp，居然把这个写出来了，有点自豪。

我做题之前瞄了一眼题解数量，5篇，心想自己是不是也能写题解试试。

然后看了一眼范围，n m<=200，心里忽然飘过一句话“200引导我们思考O(n^3)。”感觉是哪个题解里见过，觉着挺乐呵。

做完题，习惯性打开题解。

第一句话。

“200引导我们思考O(n^3)。”

我忽然就真想动动手写题解了。