IOI 2023 Day1 Soccer 题解

· · 题解

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

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

因此尝试利用这个结构来进行 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;
}