There are nn pirate chests buried in Byteland, labeled by 1,2,…,n1,2,…,n. The ii-th chest's location is (xi,yi)(xi,yi), and its value is wiwi, wiwi can be negative since the pirate can add some poisonous gases into the chest. When you open the ii-th pirate chest, you will get wiwi value.
You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.
Please write a program to find the best rectangle with maximum total value.
Input
The first line of the input contains an integer T(1≤T≤100)T(1≤T≤100), denoting the number of test cases.
In each test case, there is one integer n(1≤n≤2000)n(1≤n≤2000) in the first line, denoting the number of pirate chests.
For the next nn lines, each line contains three integers xi,yi,wi(−109≤xi,yi,wi≤109)xi,yi,wi(−109≤xi,yi,wi≤109), denoting each pirate chest.
It is guaranteed that ∑n≤10000∑n≤10000.
Output
For each test case, print a single line containing an integer, denoting the maximum total value.
Sample Input
2 4 1 1 50 2 1 50 1 2 50 2 2 -500 2 -1 1 5 -1 1 1
Sample Output
100 6
将X从小到大排序,将Y左边离散化,然后枚举x的上下界,然后“顺路”建立线段树维护最大连续区间和即可。
这个题最主要的就是建立线段树维护最大连续区间和这个操作,把原来N^3的枚举操作优化成N^2logn的复杂度。看不明白的直接下方留言就好惹~。
#include<bits/stdc++.h>
using namespace std;
int soty[2005];
#define LL long long
#define ls p<<1
#define rs p<<1|1
struct fuck { int x, y, w; }sp[2002];
bool cmp(fuck a, fuck b) {
return a.x < b.x;
}
int cnty;
int idy(int x) { return lower_bound(soty + 1, soty + cnty + 1, x) - soty; }
struct ed {
LL ll, lr, lm, sum;
}tree[2003 * 3];
inline void up(int p) {
tree[p].sum = tree[ls].sum + tree[rs].sum;
tree[p].ll = max(tree[ls].ll, tree[ls].sum + tree[rs].ll);
tree[p].lr = max(tree[rs].lr, tree[rs].sum + tree[ls].lr);
tree[p].lm = max(tree[ls].lr + tree[rs].ll, max(tree[ls].lm, tree[rs].lm));
}
void add(int l, int r, int p, int pos, LL x) {
if (l == r) {
tree[p].lm += x;
tree[p].sum = tree[p].ll = tree[p].lr = tree[p].lm;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)add(l, mid, ls, pos, x);
else add(mid + 1, r, rs, pos, x);
up(p);
}
long long dp[2005];
int main() {
int te;
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> te;
while (te--) {
int n; cin >> n;
cnty = 0;
for (int i = 1; i <= n; i++) {
cin >> sp[i].x >> sp[i].y >> sp[i].w;
soty[++cnty] = sp[i].y;
}
sort(sp + 1, sp + 1 + n, cmp);
sort(soty + 1, soty + 1 + cnty);
cnty = unique(soty + 1, soty + 1 + cnty) - soty - 1;
long long ans = 0;
for (int i = 1; i <= n; i++) {
if (i != 1 && sp[i].x == sp[i - 1].x)continue;
memset(tree, 0, sizeof tree);
for (int j = i; j <= n; j++) {
add(1, cnty, 1, idy(sp[j].y), sp[j].w);
if (j == n || sp[j].x != sp[j + 1].x) {
//cout << i << " " << j << "\n";
ans = max(ans, tree[1].lm);
}
}
}
cout << ans << "\n";
}
return 0;
}
文章浏览阅读1.7k次。一、Sqoop概述 Sqoop是一款开源的工具,主要用于在hadoop(hive)与传统数据库(mysql、Oracle、postgresql)间进行数据的传递。可以将关系型数据库中的数据导入HDFS中,也可以将HDFS中的数据导入到关系型数据库中。 将导入导出命令转换为MapReduce程序来实现。翻译出的MapReduce中主要是对inputformat和outputformat进行定制。二、安装配置Sqoop 官网:http:..._sqoop官网
文章浏览阅读207次。//// main.cpp// mach-o//// Created by Allenboy on 2018/4/16.// Copyright 2018年 Allenboy. All rights reserved.//#include <stdio.h>#include <stdlib.h>#include <mach-o/loade..._segment_command_64
文章浏览阅读1.5k次。Description从命令行输入两个日期(格式为MM,dd,yyyy),程序解析日期,判断两个日期的大小,以及两个日期的间隔天数。Input两个日期Output日期大小关系间隔天数(正数)Sample Input04,12,2012 04,21,2012Sample Output<9HINT月份是从0开始import ja..._java diffday
文章浏览阅读60次。There are hundreds of criteria for evaluating RIA and AJAX products. So many that it’s easy to lose focus and misj...
文章浏览阅读7.8k次,点赞6次,收藏71次。用过xilinx zynq petalinux的人都知道petalinux编译一次非常慢,即使下载了sstate和download包之后编译还是很慢很慢,真是让人难以接受了。。。。so....经过我一番艰苦研究之后终于弄明白了如何使用petalinux生成的sdk来编译自己的驱动程序,步骤如下:第一步:vivado搭建硬件环境,编译出xsa,在petalinux下创建工程,按照官方指导步骤最后 petalinux-build 编译一次生成整个linux工程第二步:使用petalinux-buil_petalinux交叉编译环境
文章浏览阅读3.8k次,点赞28次,收藏34次。我们在使用Docker的时候,用着别人的镜像总是差点意思又或者说会有环境差异导致的潜在问题,为了避免这些问题我们可以自行构建镜像,并且将镜像上传阿里云镜像仓库方便拉取_上传镜像
文章浏览阅读4.6k次。具体方法同 “java_home”,我的 jre_home 路径为 “D:\Program Files\Java\openjdk-11+28_windows-x64_bin\jdk-11\jre”,注意 jre 是手动生成的,因为在 openjdk11 中去除了 jre。% jre_home%\bin”,(其中 “% java_home%” 的意思为刚才设置 java_home 的值),将变量值上移。% java_home%\jre\bin”,(其中 “% java_home%” 的意思为刚才。_jdk下载
文章浏览阅读702次。本文主要为大家推荐一篇js解决软键盘遮挡输入框的问题分享,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧,希望能帮助到大家。经验须知弹出软键盘时:ios端$(‘body').scrollTop()会改变android端$(window).height()会改变拉起键盘不是一瞬间,而是有一个缓动过程问题重现ios端,经常会出现输入法遮挡输入框的问题(特别是那种有一个白色顶部的输入法,..._iphone键盘挡住了输入框js
文章浏览阅读1.1k次。你怎么还是采用asp的方式来实现呢? 既然用了datagrid再后面加一个然后为你的DataGrid添加 ItemCommand事件(this.MyList.ItemCommand += new System.Web.UI.WebControls.DataGridCommandEventHandler(this.MyList_ItemCommand)) 在这个事_commandname类 java
文章浏览阅读574次。简单邮件传输协议 (Simple Mail Transfer Protocol, SMTP) 是在Internet传输email的事实标准。SMTP是一个相对简单的基于文本的协议。(推荐学习:PHP视频教程)在其之上指定了一条消息的一个或多个接收者(在大多数情况下被确认是存在的),然后消息文本会被传输。可以很简单地通过telnet程序来测试一个SMTP服务器。SMTP使用TCP端口25。要为一个给..._phpemail 设置超时时间
文章浏览阅读313次,点赞5次,收藏4次。探索RNA测序教程:griffithlab/rnaseq_tutorial项目地址:https://gitcode.com/griffithlab/rnaseq_tutorial在这个数字化时代,生物学研究已经深入到基因表达和调控的微观层面,RNA测序(RNA-seq)成为了理解这些过程的强大工具。griffithlab/rnaseq_tutorial 是一个精心设计的开源项目,旨在为研究人...
文章浏览阅读8.9k次,点赞8次,收藏34次。文章目录设置下载源利用conda创建python3.5的环境安装tensorflow_gpu1.15.0首先我们需要安装anaconda,这个需要读者自动解决。设置下载源在windows系统自己用户的目录下面新建一txt文件,更名为.condarc,写入以下信息channels: - defaultsshow_channel_urls: truedefault_channels: - https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/m_windows tensorflow1.15下载