题解 P2706 【巧克力】

顾z

2018-10-26 18:28:51

Solution

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 表示很水的一个题.~~要不是数据有问题我就切了~~ **悬线法+二维前缀和**。吼啊 ~~不过貌似比只写二维前缀和的麻烦一点.~~ 我们预处理出来悬线法用的数组.(记得变一下限制条件. 然后真正做悬线法的时候. 我们可以**得到一个合法矩形**. 其左上角坐标,右下角坐标均可求. 然后用二维前缀和算一下即可. PS:这题数据有问题,读入矩阵的时候要用$cin$ ``代码`` ```c++ #include<cstdio> #include<algorithm> #include<iostream> #define R register #define N 308 using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,ans; int res[N][N],sum[N][N]; int ri[N][N],le[N][N],up[N][N]; inline int calc(int a,int b,int c,int d) { return (sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1]); } int main() { in(n),in(m); for(R int i=1;i<=n;i++) for(R int j=1;j<=m;j++) { cin>>res[i][j]; sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+res[i][j]; ri[i][j]=le[i][j]=j; up[i][j]=1; } for(R int i=1;i<=n;i++) for(R int j=2;j<=m;j++) if(res[i][j] and res[i][j-1]) le[i][j]=le[i][j-1]; for(R int i=1;i<=n;i++) for(R int j=m-1;j>=1;j--) if(res[i][j] and res[i][j+1]) ri[i][j]=ri[i][j+1]; for(R int i=1;i<=n;i++) for(R int j=1;j<=m;j++) { if(res[i][j] and res[i-1][j]) { le[i][j]=max(le[i][j],le[i-1][j]); ri[i][j]=min(ri[i][j],ri[i-1][j]); up[i][j]=up[i-1][j]+1; } int a=i-up[i][j]+1,b=le[i][j],c=i,d=ri[i][j]; ans=max(ans,calc(a,b,c,d)); } printf("%d",ans); } ```