视频剪辑软件 设计模式 node.js XML解析 canal安装 Pytorch silverlight scope Modernizr linux内存管理 外卖系统源码 java两个数组合并 windows杀死进程命令 winbox使用教程 css鼠标悬浮样式 flutter项目案例 linux重启mysql python下载安装教程 javaswitch javafile java文件 java求和 java中数据类型 java运行环境 音频频谱分析软件 电池救星 js上传图片 临时会话 图片转pdf免费软件 脚本网站 华为mate8和p9哪个好 camworks ae渲染设置 cdr怎么填充颜色 太阳代理ip 迅捷pdf转换器官网 id书籍排版教程 包图小白体 cad如何旋转图形 护魂者的命运
当前位置: 首页 > 学习教程  > 编程语言

1495. 宝石

2020/8/11 20:05:30 文章标签:

Description

见上帝动了恻隐之心,天后也想显示一下慈悲之怀,随即从口袋中取出一块魔术方巾,让身边的美神维纳斯拿到后堂的屏风上去试试,屏风是正方形的,高和宽方向上各划有m条鱼屏风的边平行的直线,平行直线间的距离为1厘米。这2m条直线共有m*m个交点,在某些交点上镶嵌着宝石。如果魔术方巾的边与屏风的边平行且魔术方巾触碰到屏风上镶嵌着的宝石,就将与这些宝石等值的金银送给人们。维纳斯想让魔术方巾触碰到的宝石的价值最多,可要在短短的1秒钟之内解决问题,也感到力不从心,你能帮帮她吗?

Input

输入文件gem.in的第一行有三个正整数m,n,k,数与数之间用一个空格分隔。其中m为屏风在高和宽方向上被划分出的直线数。魔术方巾为正方形的,它的边长为k厘米。N为屏风上宝石的个数。
接下来的n行,每行三个正整数,依次表示宝石所在直线的行号、列号、宝石的价值,数与数之间用一个空格分隔。

Output

输出文件gem.out只有一个正整数,为魔术方巾触碰到的宝石的最大价值总数。

Sample Input

10    4    4
1     1    9
2     3    5
6     2    12
4     5    6

Sample Output

23

Data Constraint

Hint

【输入样例2】
10 4 3
1 1 9
2 3 5
6 2 12
4 5 6
【输出样例2】
18

【数据限制】
30%的数据,1≤m≤500,1≤n≤10000,1≤k≤100;
60%的数据,1≤m≤3000,1≤n≤10000,1≤k≤1000;
100%的数据,1≤m≤50000,1≤n≤50000,1≤k≤10000;

Solution

对于每个点,按照x坐标排序,将所有的val放进y所在的位置,如果x超出k的范围就将前面小于x-k的删掉。

当所有的同样的x放完之后,做一遍前缀和,扫描s[ i ]-s[ i-k ]的最大值即可。

时间O(nm)。

考虑优化。

设线段树上叶子结点x,表示从i~i+k的区间的价值和。

其他上面的节点表示下面的所有区间的价值的最大值。

每次加入节点,将y-k~y的所有位置区间加标记。

然后每次全局查询即可。

时间O(n log m)。

Code

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define ls x<<1
#define rs ls|1
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 50020
using namespace std;
I n,m,k,q[N],l,r;
ll ans,f[N],c[N],tr[N<<2],lzy[N<<2],now;
struct node{I x,y;ll v;}a[N];
void R(I &x){
	I p=1;x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') p=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	x*=p;
}
I cmp(node x,node y){return x.x<y.x;}
void down(I x){
	if(!lzy[x]) return;
	tr[ls]+=lzy[x],tr[rs]+=lzy[x];
	lzy[ls]+=lzy[x],lzy[rs]+=lzy[x];
	lzy[x]=0;
}
void ins(I l2,I r2,I val,I x=1,I l=1,I r=n){
	if(l>r2||r<l2) return;
	if(l>=l2&&r<=r2){
		tr[x]+=val,lzy[x]+=val;
		return;
	}
	down(x);
	I M=l+r>>1;
	ins(l2,r2,val,ls,l,M),ins(l2,r2,val,rs,M+1,r);
	tr[x]=max(tr[ls],tr[rs]);
}
I main(){
	freopen("gemstone.in","r",stdin);
	freopen("gemstone.out","w",stdout);
	R(n),R(m),R(k);k++;
	F(i,1,m){
		scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].v);
	}
	sort(a+1,a+1+m,cmp);
	l=1,r=0;
	F(i,1,m){
		q[++r]=i;
		ins(max(a[i].y-k+1,0),a[i].y,a[i].v);
		now+=a[i].v;
		//ins(r);
		if(a[i].x!=a[i+1].x){
			while(l<=r&&a[q[l]].x<a[i].x-k+1){
				ins(max(a[q[l]].y-k+1,0),a[q[l]].y,-a[q[l]].v);
				now-=a[q[l]].v;
				//del(l);
				l++;
			}
			if(now<=ans) continue;
			ans=max(ans,tr[1]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

 


本文链接: http://www.dtmao.cc/news_show_100285.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?