自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:50:01，当前版本为作者最后更新于2023-09-01 15:42:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题很有趣啊，感觉自己想出来这个题的过程非常有趣。

让我们先来编一个合法条件，一种简洁的刻画方式是：若干个长度区间不断扩张宽度区间不断缩短的矩阵的并。

因此尝试利用这个结构来进行 dp，一个直观的想法是我们枚举最长的那个矩形覆盖了哪一列，然后在这一列上对行区间进行 dp。具体是 $dp_{l,r}$ 表示当前矩形行区间为 $[l,r]$ 然后继续选择矩形的最大答案，显然列区间一定是能取满就取满。

设 $(L,R)$ 为列区间，转移显然是从第 $L$ 或 $R$ 列上限制住 $[l,r]$ 的那些 $1$ 的空隙里面转移过来，一种方便的写法是发现第 $l$ 行和第 $r$ 行不会同时被空隙包含，所以直接考虑把这一行去掉的贡献即可，即 $dp_{l,r}=\max(dp_{l+1,r},dp_{l,r-1})+R-L-1$。

这个做法是 $O(n^3)$ 的，配合上特判只能通过 $77.5$ 分。

实际上上面这个做法有很多可以优化的地方。首先我们考虑如何抛开枚举哪一列这个步骤来刻画状态中的所谓“空隙”。直接用行区间 $l,r$ 刻画显然会有重复。但是如果我们用 $l-1$ 行上的某一个 $1$ 的位置与 $r$ 来刻画这个空隙，就不会有重复了，并且状态数仍然是 $O(n^2)$ 的，因为要保证这个 $1$ 下面一直到第 $r$ 行都没有别的 $1$。

也就是说，我们可以直接用矩阵上的一个位置来表示一个空隙。我们将空隙而接下来转移也很简单，跟上面一样，每次要么 $r$ 这一行不被包含在下一个空隙里直接算贡献，要么就转移到左边或右边最下面的一个空隙中即可。

对于每个空隙求列区间 $(L,R)$ 以及整个 dp，都可以在 $O(n^2)$ 的时间内完成。代码实现非常之简洁啊！这个题真是太美了。

#include "soccer.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
// #define int ll
#define N 2005
using namespace std;
namespace 
{
    int dp[N][N];
    int pos[N][N];
    int L[N][N],R[N][N];
}
int biggest_stadium(int n, std::vector<std::vector<int>> aa)
{
    int ans=0;
    vector<vector<pa>>tong(n+1,vector<pa>());
    for (int j=1;j<=n;j++)
    {
        for (int i=1;i<=n;i++)
        {
            dp[i][j]=0;
            if(aa[i-1][j-1]) pos[i][j]=i;
            else pos[i][j]=pos[i-1][j];
            tong[i-pos[i][j]].push_back(mp(i,j));
        }
    }
    for (int i=1;i<=n;i++)
    {
        L[i][0]=0;
        for (int j=1;j<=n;j++)
            if (aa[i-1][j-2]) L[i][j]=j-1;else L[i][j]=L[i][j-1];
        R[i][n+1]=n+1;
        for (int j=n;j>=1;j--)
            if (aa[i-1][j]) R[i][j]=j+1;else R[i][j]=R[i][j+1];
    }
    for (int d=1;d<=n;d++)
    {
        for (auto [i,j]:tong[d])
        {
            if (pos[i][j]!=i-1)
            {
                R[i][j]=min(R[i][j],R[i-1][j]);
                L[i][j]=max(L[i][j],L[i-1][j]);
            }
            dp[i][j]=dp[i-1][j]+R[i][j]-L[i][j]-1;
            if (L[i][j]>0)
            {
                int len=pos[i][L[i][j]]-pos[i][j];
                dp[i][j]=max(dp[i][j],dp[i][L[i][j]]+len*(R[i][j]-L[i][j]-1));
            }
            if (R[i][j]<=n)
            {
                int len=pos[i][R[i][j]]-pos[i][j];
                dp[i][j]=max(dp[i][j],dp[i][R[i][j]]+len*(R[i][j]-L[i][j]-1));
            }
            ans=max(ans,dp[i][j]);
        }
    }
    return ans;
}