题目描述

题目大意

在一个 m×m m × m 的矩阵上有 n n 个点，它们都有各自的代价，现在求最大边长为kk的子矩阵代价和

解题思路

10分纯离散 60分暴力+前缀和优化 100分 扫描线+线段树+离散化

就是把从坐标离散化，然后扫描，用线段树维护区间最大值就行了

10分代码

#include<cstdio> #include<algorithm> using namespace std;int n,m,k,sum1,sum2,ans; struct node{int x,y,num;}a[50001]; bool cmp(node x,node y){return x.y<y.y;} int main() { scanf("%d%d%d",&m,&n,&k); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].num); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { sum1=a[i].num;sum2=a[i].num; for(int j=i+1;j<=n;j++) { if(a[i].y+k<a[j].y)break;//够不到就跳过 if(a[i].x>=a[j].x&&a[i].x-a[j].x<=k) sum1+=a[j].num; if(a[i].x<=a[j].x&&a[j].x-a[i].x<=k) sum2+=a[j].num; } ans=max(ans,max(sum1,sum2)); } printf("%d",ans); }

60分代码

转载至 WYC W Y C

#include<cstdio> #include<algorithm> using namespace std; int m,n,k,x,y,c,f[3001][3001],maxs; int main() { scanf("%d%d%d",&m,&n,&k); for (int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&c); f[x][y]+=c; } for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) f[i][j]+=f[i][j-1]+f[i-1][j]-f[i-1][j-1]; for (int i=k+1;i<=m;i++) for (int j=k+1;j<=m;j++) { maxs=max(maxs,f[i][j]-f[i][j-k-1]-f[i-k-1][j]+f[i-k-1][j-k-1]); } printf("%d",maxs);

100分代码

#include<cstdio> #include<algorithm> #define lson (k<<1) #define rson (k<<1|1) #define M 100005 #define N 250025 using namespace std;int n,m,k,tree[N],lazy[N],left[N],right[N],b[M],tot,cnt,ans; struct node{int l,r,num,h;}a[M]; bool cmp(node x,node y) { if(x.h!=y.h) return x.h<y.h; return x.num<y.num; } void build(int k,int l,int r)//建树 { left[k]=l;right[k]=r; lazy[k]=0;tree[k]=0; if(l==r) return; int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); } int find(int num,int l,int r)//查找在b中的位置 { while(l<=r) { int mid=(l+r)>>1; if(b[mid]==num) return mid; if(b[mid]<num) l=mid+1;else r=mid-1; } return l; } void add(int k,int l,int r,int d) { if(l==left[k]&&right[k]==r) { tree[k]+=d; lazy[k]+=d; return; } int mid=(left[k]+right[k])>>1; lazy[lson]+=lazy[k];lazy[rson]+=lazy[k]; tree[lson]+=lazy[k];tree[rson]+=lazy[k]; lazy[k]=0; if(r<=mid) add(lson,l,r,d); else if(l>mid) add(rson,l,r,d); else { add(lson,l,mid,d); add(rson,mid+1,r,d); } tree[k]=max(tree[lson],tree[rson]); } int main() { scanf("%d%d%d",&m,&n,&k); for(int i=1,x,y,z;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); b[++tot]=x; a[tot].l=x;a[tot].r=min(x+k+1,m+1);//因为不可以超出范围，所以要用min，以下同上 a[tot].h=y;a[tot].num=z; b[++tot]=min(x+k+1,m+1); a[tot].l=x;a[tot].r=min(x+k+1,m+1), a[tot].h=min(y+k+1,m+1);a[tot].num=-z; } sort(a+1,a+1+tot,cmp); sort(b+1,b+1+tot); cnt=1; for(int i=2;i<=tot; i++) if (b[i]!=b[i-1])b[++cnt]=b[i];//离散化or去重 build(1,1,cnt-1);//建树 for(int i=1,x1,x2;i<=tot;i++) { x1=find(a[i].l,1,cnt); x2=find(a[i].r,1,cnt)-1; if(x1<=x2) add(1,x1,x2,a[i].num);//区间增值 ans=max(ans,tree[1]);//返回最大值 } printf("%d",ans);//输出 }