国外镜像 华为鸿蒙 ssl events arraylist jdbc reference jboss Normalizecss android实战项目 在线考试系统代码 jquery删除子元素 matlab根号怎么打出来 mac安装hadoop 当前时间减一天 python数据库 python解析json数据 python生成多个随机数 python自学教程 python安装环境变量 python如何调用函数 java课程学习 java中new java删除文件 java怎么获取当前时间 心理学与生活下载 快捷精灵 手机主题之家 p6软件 苍灵世界 js验证码 免费微信答题制作 电脑代码雨 谷歌浏览器访问助手 sendto函数 文件分割 画图3d opengl版本过低 cdr怎么复制图形 方正gbk
当前位置: 首页 > 学习教程  > 编程语言

JZOJ2020年8月11日提高组T2 宝石

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

JZOJ2020年8月11日提高组T2 宝石

题目

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

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;

Hint

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

题解

题意

给出nn个宝石,每个宝石都有一定的价值
可以放置一个kkk*k的矩阵
问如何放置使得价值最大
问最大价值

分析

将题目转换一下
nnkkk*k的矩阵,每个矩阵都有一定的价值,问一个最大价值的重叠矩阵
容易想到扫描线
按照纵坐标排序
维护两个指针
一个是加入(ii),一个是删除(jj)
那么当jj的纵坐标+kk小于ii的纵坐标时,删掉jj
可以用线段树来维护区间修改
然后每操作一次就用树顶来更新答案

Code

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int x,y,z,flag;
}a[50005];
int n,m,k,i,ans,tot,tree[200005],lazy[200005];
bool cmp(node x,node y)
{
    return x.y<y.y;
}
void update(int x)
{
    if (lazy[x]!=0)
    {
        lazy[x<<1]+=lazy[x];
        lazy[x<<1|1]+=lazy[x];
        tree[x<<1]+=lazy[x];
        tree[x<<1|1]+=lazy[x];
        lazy[x]=0;
    }
}
void modify(int now,int l,int r,int p,int q,int x,int bj)
{
    if (l>=p&&r<=q)
    {
        tree[now]+=x*bj;
        lazy[now]+=x*bj;
        return;
    }
    int mid=(l+r)>>1;
    update(now);
    if (p<=mid) modify(now<<1,l,mid,p,q,x,bj);
    if (q>mid) modify(now<<1|1,mid+1,r,p,q,x,bj);
    tree[now]=max(tree[now<<1],tree[now<<1|1]);
}
int main()
{
    scanf("%d%d%d",&m,&n,&k);
    for (i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+n+1,cmp);
    tot=1;
    for (i=1;i<=n;i++)
    {
        modify(1,1,m,a[i].x,min(a[i].x+k,m),a[i].z,1);
        while (a[i].y==a[i+1].y)
        {
            i++;
            modify(1,1,m,a[i].x,min(a[i].x+k,m),a[i].z,1);
        }
        while (a[tot].y+k<a[i].y)
        {
            modify(1,1,m,a[tot].x,min(a[tot].x+k,m),a[tot].z,-1);
            tot++;
        }
        ans=max(ans,tree[1]);
    }
    printf("%d\n",ans);
    return 0;
}

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

附件下载

上一篇:1495. 宝石

下一篇:redis.conf 配置详情

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?