题解 P3135 【[USACO16JAN]Fort Moo P】

· · 题解

前言

我又双叒叕来水沝淼㵘题解了

这道题的思路大概是指针 + 暴力枚举 以及悬针法优化。

（不是很懂为什么会出现动态规划的标签）

具体做法：

相信一道叫玉蟾宫的题目大家都做过。

那道题的一个最重要的技巧就是悬针法（这个不会的可以到玉蟾宫的题解那里学）。

这道题的数据范围很显然的来看 O(n^4) 是过不了的.....

思考如何优化至 O(n ^ 3)。

不难发现我们肯定要预处理每一个点向上以及向右最远能扩展的地方(可以 n^2 或者 n^3 预处理，影响不大)。

然后我们枚举两行，就假定为 i 行以及 j 行，不妨钦定 i < j

然后枚举第 j 行 的所有列 k ， 如果第 j 行的第 k 列那一个点，最远能到达的最上面的点的横坐标小于等于 i , 那么就说第 k 列是备选点，放入队列。

接下来就好办了，这些备选点中(肯定是按照列号递增的)，有些点是可以构成一个框架的，但是有一些是无法连接的，这个在前面说到的悬针法可以预处理出来。

我们借助一个指针，枚举当前可选点最远能扩展到的可选点，不难发现这个指针是只增不减的，同时下一次枚举的起点就是现在指针的位置了（这个应该也很容易想到，因为枚举当前起点和当前指针的中间的点是没有意义的），那么总的时间复杂度就是 O(n ^ 3) 的了。

一个小细节就是当扩展不了的时候就强制从指针的下一个位置开始枚举，还有就是注意移动指针的时候要取上下两个点的 min ，因为是要形成一个矩形框架，不能一边长一边短，因此要取 min。

Code

(本人较菜，上面可能不是很清楚，看看代码吧)

#include <bits/stdc++.h>
using namespace std;
int H[505][505],R[505][505],vis[505];
char mp[505][505];
int n,m;
int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n; i ++)
        cin >> mp[i] + 1;
    memset(H,0x3f,sizeof(H));//一开始一定要初始化
    memset(R,0,sizeof(R));
    //我选择的是n^3预处理
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= m ; j ++)
        {
            if(mp[i][j] == 'X') continue;
            for(int k = i ; k >= 1 ; k --)
            {
                if(mp[k][j] == 'X') break;
                H[i][j] = k;//悬针法求向上面能够到达的最远点
            }
            for(int k = j ; k <= m ; k ++)
            {
                if(mp[i][k] == 'X') break;
                R[i][j] = k;//悬针法求向右能够到达的最远点
            }
        }
    }
    int Ans = -1;
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = i + 1; j <= n ; j ++)
        {
            int tail = 0;
            for(int k = 1 ; k <= m ; k ++)
            if(H[j][k] <= i) tail ++ , vis[tail] = k;//可选点入队
            int Now = 0;//Now表示指针
            while(Now <= tail)
            {
                int x = Now;
                while(min(R[i][vis[x]],R[j][vis[x]]) >= vis[Now + 1] && Now < tail) Now ++;
                //注意取min，然后判断向右能扩展的最远点是否大于等于指针指到的可选点即可，最后取到的就是最远能够扩展到的可选点
                if(x == Now) {Now ++ ;continue;}//扩展不动了强行移动
                Ans = max(Ans, (vis[Now] - vis[x] + 1) * (j - i + 1));//底乘高得到面积，最终答案取Max
            }
        }
    }
    cout << Ans;
    return 0;
}