NC24239. [USACO 2019 Feb G]Painting the Barn
描述
We can describe the side of the barn as a 2D x-y plane, on which Farmer John paints N rectangles, each with sides parallel to the coordinate axes, each described by the coordinates of its lower-left and upper-right corner points.
Farmer John wants to apply several coats of paint to the barn so it doesn't need to be repainted again in the immediate future. However, he doesn't want to waste time applying an excessive number of coats of paint. It turns out that K coats of paint is the optimal amount. However, looking at the amount of area covered by K coats of paint, he is not very happy. He is willing to paint up to two additional rectangles to try and increase this area, as long as these two rectangles are disjoint (not sharing any positive amount of area in common). Note that he can also decide to paint zero new rectangles or just one new rectangle if this ends up being the best thing to do.
输入描述
The first line of input contains N and K (1≤K,N≤10^5). Each of the remaining NN lines contains four integers x1,y1,x2,y2describing a rectangular region being painted, with lower-left corner (x1,y1) and upper-right corner (x2,y2). All x and y values are in the range 0…200, and all rectangles have positive area.
Like the rectangles he already painted, any new rectangles that Farmer John paints must have positive area, and their corner points must have x and y coordinates in the range 0…200.
输出描述
Please output the maximum area of the barn that could be covered by exactly K coats of paint, if Farmer John paints up to two additional disjoint rectangles.
示例1
输入:
3 2 1 1 4 4 3 3 7 6 2 2 8 7
输出:
26
C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 1032K, 提交时间: 2020-08-13 19:41:08
#include<bits/stdc++.h>
using namespace std;
int mp[205][205];
int nmp[205][205];
int sum1[205][205];
int sum2[205][205];
int dp[205];
int li[205],ri[205],up[205],dw[205];
int main(){
int n,k;
scanf("%d%d",&n,&k);
int x1,y1,x2,y2;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1++,y1++,x2++,y2++;
mp[x1][y1]++;mp[x1][y2]--;
mp[x2][y1]--;mp[x2][y2]++;
}
int cnt=0;
for(int i=1;i<=200;i++){
for(int j=1;j<=200;j++){
mp[i][j]+=mp[i][j-1]+mp[i-1][j]-mp[i-1][j-1];
if(mp[i][j]==k){
nmp[i][j]=-1;
cnt++;
}
else if(mp[i][j]==k-1){
nmp[i][j]=1;
}
}
}
//printf("%d\n",cnt);
for(int j=1;j<=200;j++){
for(int i=1;i<=200;i++){
sum1[i][j]=sum1[i-1][j]+nmp[i][j];
}
}
for(int i=1;i<=200;i++){
for(int j=1;j<=200;j++){
sum2[i][j]=sum2[i][j-1]+nmp[i][j];
}
}
int ans=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=200;i++){
for(int j=i;j<=200;j++){
for(int k=1;k<=200;k++){
int tmp=sum1[j][k]-sum1[i-1][k];
dp[k]=max(0,max(tmp,dp[k-1]+tmp));
li[k]=max(li[k],dp[k]);
}
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=200;i++){
for(int j=i;j<=200;j++){
for(int k=200;k>=1;k--){
int tmp=sum1[j][k]-sum1[i-1][k];
dp[k]=max(0,max(tmp,dp[k+1]+tmp));
ri[k]=max(ri[k],dp[k]);
}
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=200;i++){
for(int j=i;j<=200;j++){
for(int k=1;k<=200;k++){
int tmp=sum2[k][j]-sum2[k][i-1];
dp[k]=max(0,max(tmp,dp[k-1]+tmp));
up[k]=max(up[k],dp[k]);
}
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=200;i++){
for(int j=i;j<=200;j++){
for(int k=200;k>=1;k--){
int tmp=sum2[k][j]-sum2[k][i-1];
dp[k]=max(0,max(tmp,dp[k+1]+tmp));
dw[k]=max(dw[k],dp[k]);
}
}
}
for(int i=1;i<=200;i++){
li[i]=max(li[i],li[i-1]);
up[i]=max(up[i],up[i-1]);
}
for(int i=200;i>=1;i--){
ri[i]=max(ri[i],ri[i+1]);
dw[i]=max(dw[i],dw[i+1]);
}
for(int i=1;i<=200;i++){
ans=max(ans,li[i]+ri[i+1]);
ans=max(ans,up[i]+dw[i+1]);
}
//printf("%d\n",ans);
printf("%d\n",cnt+ans);
return 0;
}
C++ 解法, 执行用时: 30ms, 内存消耗: 1532K, 提交时间: 2022-02-25 10:35:29
#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;
}