intellij idea使用教程 整数转换 MongoDB Nginx https 金融信贷 云计算架构 winforms selenium reference ide vue学习教程 photoshop视频教程全集下载 sql视频教程 matlab求矩阵最大值 mysql修改字段值 mysql组合索引 linux查看jdk安装路径 python的str python创建对象 python开发界面 randomjava java替换字符串 java连接sql linux启动 unix操作系统下载 groupby 数据库系统概论第五版 din字体 视频加字幕软件哪个好 h370主板 beatedit gilisoft fireworks8序列号 多面硬币 tar解压 给视频加字幕的软件 iar下载 算法笔记 ios删除描述文件
当前位置: 首页 > 学习教程  > 编程语言

JZOJ2020年提高组T2 宝石

2020/8/11 20:01:12 文章标签:

JZOJ2020年提高组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_100274.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?