Description

link

大意：

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

Solution

这俩 \(F\) 题可以用一种标准解法完成（线段树或单调队列优化 \(dp\) ）

首先要看出来这个是一个 \(dp\) 题（这一步应该很好想到把）

然后想到要容斥，就是要先算总的（不考虑覆盖只算一次）减去覆盖的值

记\(S_{i,j}\) 为第 \(i\) 行的前缀和

然后枚举我们当前选择的区间，就有转移方程

这里和谐了，博主不会打大括号……或者参考wucstdio‘s solution

（其实就是用 \(g\) 维护一个去掉重复的，然后用 \(f\) 再添上新增的）

然后我们发现这样算复杂度是 \(O(nm^2)\) 的，我们并不能接受

然后我们更改一下需要维护的量，让线段树去维护它就好了

\(O(nm \space logm)\)

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar(); 
        return res*f;
    }
    const int N=1e5+10;
    struct tree{
        int maxx[N<<2]; 
        #define maxx(p) maxx[p]
        inline void push_up(int p){return maxx(p)=max(maxx(p<<1),maxx(p<<1|1)),void();}
        inline void change(int p,int l,int r,int x,int d)
        {
            if(l==r) return maxx(p)=d,void();
            int mid=(l+r)>>1; if(x<=mid) change(p<<1,l,mid,x,d); else change(p<<1|1,mid+1,r,x,d);       
            return push_up(p),void();
        }
        inline int ask(int p,int l,int r,int L,int R)
        {
            if(R<L) return -1e15-10;
            if(L<=l&&r<=R) return maxx(p);
            int mid=(l+r)>>1,ans=-1e15-10;
            if(L<=mid) ans=max(ans,ask(p<<1,l,mid,L,R));
            if(R>mid) ans=max(ans,ask(p<<1|1,mid+1,r,L,R));
            return ans;
        }
    }t1,t2,t3;
    int n,m,l,a[55][20010],s[55][20010],f[20010];
    signed main()
    {
        n=read(); m=read(); l=read();
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=read(),s[i][j]=s[i][j-1]+a[i][j];
        for(int i=1;i<N;++i) t1.maxx[i]=t2.maxx[i]=t3.maxx[i]=-1e15-10;
        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));
                f[j]=max(f[j],t2.ask(1,1,m,j-l+1,j)+s[i][j-1]);
                f[j]=max(f[j],t3.ask(1,1,m,j+1,j+l)-s[i][j+l-1]);
                if(f[j]<0) f[j]=0;
            }
            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.change(1,1,m,j,f[j]); 
                t2.change(1,1,m,j,f[j]-s[i+1][j+l-1]); 
                t3.change(1,1,m,j,f[j]+s[i+1][j-1]);
            }
        } printf("%lld\n",t1.ask(1,1,n,1,n));
        return 0;
    }
}
signed main(){return yspm::main();}

Codeforces1304F Animal Observation

原文：https://www.cnblogs.com/yspm/p/12319112.html