5873. 小p的属性

xiaoxiao2021-03-01  20

题目大意:

思路:

把问题转化一下,就是在一个二维的平面上,有些点有权值,你每次都可以向右或者向上走,经过一个点后得到他的权值,并且每走一步都会再次加上他的权值,问你走k步的最大权值是多少,k=10e9。 我们发现他每次走都会走到某个点上,这样答案才会更优,所以我们把所有点的横坐标纵坐标拿出来离散,然后插入点值,这样就可以不用枚举坐标了。先预处理前缀和!

程序:

#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #define N 2005 #define LL long long using namespace std; struct data{LL x,y,z;}x[N]; LL sum[N][N],f[N][N],b[N]; LL n,m,size,cnt; int main(){ freopen("growth.in","r",stdin); freopen("growth.out","w",stdout); scanf("%lld%lld",&n,&m); for (int i=1;i<=n;i++) { scanf("%lld%lld%lld",&x[i].x,&x[i].y,&x[i].z); } for (int i=1;i<=n;i++) b[++cnt]=x[i].x,b[++cnt]=x[i].y; sort(b+1,b+cnt+1); size=unique(b+1,b+cnt+1)-b-1; for (int i=1;i<=n;i++){ x[i].x=lower_bound(b+1,b+size+1,x[i].x)-b; x[i].y=lower_bound(b+1,b+size+1,x[i].y)-b; sum[x[i].x][x[i].y]+=x[i].z; } for (int i=1;i<=size;i++) for (int j=1;j<=size;j++){ sum[i][j]=sum[i-1][j]+sum[i][j-1]+sum[i][j]-sum[i-1][j-1]; } for (int i=1;i<=size;i++) for (int j=1;j<=size;j++){ if (i==1&&j==1) continue; f[i][j]=max(f[i-1][j]+sum[i-1][j]*(b[i]-b[i-1]-1),f[i][j-1]+sum[i][j-1]*(b[j]-b[j-1]-1))+sum[i][j]; } LL ans=0; for (int i=1;i<=size;i++) for (int j=1;j<=size;j++) if (b[i]+b[j]<=m){ ans=max(ans,f[i][j]+sum[i][j]*(m-b[i]-b[j])); } printf("%lld\n",ans); }
转载请注明原文地址: https://www.6miu.com/read-3850309.html

最新回复(0)