题解 CF1304F2 【Animal Observation (hard version)】

wucstdio · 2020-02-16 11:31:33 · 题解

不得不说打这一场是真的爽……

这道题我写的是 O(nm\log m) 的线段树解法，但是好像还有单调队列的 O(nm) 解法。

题目大意

给你一个 n\times m 的矩形，每一个格子里面有一个数字，你可以在每一行里选择一个 2\times k 的矩形（这个矩形跨越两行），要求最后所有你选择的矩形的并的权值和最大。

数据范围

解题过程

首先我们注意到可以 DP。

设 f_{i,j} 表示处理完了前 i-1 行，其中第 i-1 行选择的区间是 [j,j+k-1]，当前覆盖的格子的最大权值。

令 S_{i,j}=\sum_{k=1}^ja_{i,k}，枚举当前行选择的区间，我们可以得到转移方程：

也就是减去重复的再加上新覆盖的。直接转移是 O(nm^2) 的。

我们设 x_{i,j}=f_{i,j}-S_{i,j+k-1},y_{i,j}=f_{i,j}+S_{i,j-1}，则上式变为：

我们需要维护出 x,y,f 三个数组，实现单点修改和区间取 \max，可以用线段树轻松实现。

时间复杂度为 O(nm\log m)。

代码

注意代码里面的 k 和 l 与题目中的 k 和 l 意义是相反的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define lc x<<1//相比之前我现在的码风发生了一些微小的改变
#define rc x<<1|1
#define mid ((l+r)>>1)
using namespace std;
struct Tree//线段树
{
    ll maxv[80005];
    void pushup(int x)
    {
        maxv[x]=max(maxv[lc],maxv[rc]);
    }
    void update(int x,int l,int r,int p,ll v)
    {
        if(l==r)
        {
            maxv[x]=v;
            return;
        }
        if(p<=mid)update(lc,l,mid,p,v);
        else update(rc,mid+1,r,p,v);
        pushup(x);
    }
    ll ask(int x,int l,int r,int from,int to)
    {
        if(from>to)return -1e12;
        if(l>=from&&r<=to)return maxv[x];
        ll ans=-1e12;
        if(from<=mid)ans=max(ans,ask(lc,l,mid,from,to));
        if(to>mid)ans=max(ans,ask(rc,mid+1,r,from,to));
        return ans;
    }
};
Tree t1,t2,t3;//t1,t2,t3分别维护f,x,y
int n,m,l;
ll a[55][20005],s[55][20005],f[20005];
int main()
{
    scanf("%d%d%d",&n,&m,&l);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        scanf("%lld",&a[i][j]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        s[i][j]=s[i][j-1]+a[i][j];
    for(int i=1;i<=80000;i++)
      t1.maxv[i]=t2.maxv[i]=t3.maxv[i]=-1e12;//注意初值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j+l-1<=m;j++)
        {
            f[j]=max(t1.ask(1,1,m,1,j-l),t1.ask(1,1,m,j+l,m));//case 1
            f[j]=max(f[j],t2.ask(1,1,m,j-l+1,j)+s[i][j-1]);//case 2
            f[j]=max(f[j],t3.ask(1,1,m,j+1,j+l)-s[i][j+l-1]);//case 3
            f[j]=max(f[j],0ll);
        }
        for(int j=1;j+l-1<=m;j++)
        {
            f[j]=f[j]+s[i][j+l-1]-s[i][j-1]+s[i+1][j+l-1]-s[i+1][j-1];
            t1.update(1,1,m,j,f[j]);
            t2.update(1,1,m,j,f[j]-s[i+1][j+l-1]);
            t3.update(1,1,m,j,f[j]+s[i+1][j-1]);//单点修改
        }
    }
    printf("%lld\n",t1.ask(1,1,n,1,n));
    return 0;
}