题解 P6100 【[USACO19FEB]Painting the Barn G】

Time_tears · 2020-09-04 15:53:50 · 题解

提供一篇 O(200^3+n) 的题解

• 首先看完本题，一定知道直接对每个位置加 1 是绝对没有出路的，所以我们首先需要用一个差分处理一下每个位置的值，这部分复杂度是 O(200^2+n) 的。

• 然后，我们要想，什么样的位置会对 answer 有影响呢？ 当然是值为 k-1,k 的位置，首先我们用一个 sum 记录下值为 k 的位置数量。然后我们就发现，给区间加 1 后，值为 k 的位置贡献为 -1 ，值为 k-1 的贡献为 1 ，然后我们枚举 i,j 把第 i 至 j 的数给提出来，用一次最大连续子段和，这样就能求出以 (i,j) 为右下节点的最大的值，再反过来做一次，就能求出以 (i,j) 为左上节点的最大的值

• 因为是求两个区间，所以最后再用一次 dp 即可。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<cstdio>
#define N 205
using namespace std;
int k,e[N][N],f[N][N],d[N][N],ans;
int n,a[N][N],b[N][N],c[N][N],sum;
const int Mxdt=200000;
inline char gc() {
    static char buf[Mxdt],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    int res=0,bj=0;
    char ch=gc();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
    return bj?-res:res;
}
inline int max(int x,int y) {
    return x>y?x:y;
}
int main() {
    n=read(),k=read();
    for(int i=1,x1,y1,x2,y2; i<=n; ++i)++a[x1=read()+1][y1=read()+1],++a[x2=read()+1][y2=read()+1],--a[x1][y2],--a[x2][y1];
    for(int i=1; i<=200; ++i)
        for(int j=1; j<=200; ++j) {
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1],b[i][j]=b[i][j-1];
            if(a[i][j]==k)--b[i][j],++sum;
            if(a[i][j]==k-1)++b[i][j];
        }
    for(int i=1; i<=200; ++i)
        for(int j=i; j<=200; ++j) {
            for(int k=1,len=0; k<=200; ++k)c[k][j]=max(c[k][j],len=max(0,len)+b[k][j]-b[k][i-1]);
            for(int k=200,len=0; k; --k)d[k][i]=max(d[k][i],len=max(0,len)+b[k][j]-b[k][i-1]);
        }
    for(int i=200; i; --i)
        for(int j=200; j; --j)f[i][j]=max(max(f[i+1][j],f[i][j+1]),d[i][j]);
    for(int i=1; i<=200; ++i)
        for(int j=1; j<=200; ++j)e[i][j]=max(max(e[i-1][j],e[i][j-1]),c[i][j]),ans=max(ans,sum+e[i][j]+max(f[i+1][1],f[1][j+1]));
    printf("%d",ans);
    return 0;
}