hdu6638 线段树求最大子段和
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6638
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.
In each test case, there is one
integer n(1≤n≤2000) in the first line, denoting the number of pirate chests.
For the next
n lines, each line contains three integers xi,yi,wi(−109≤xi,yi,wi≤109) , denoting each pirate chest.
It is guaranteed that ∑n≤10000 .
integer, denoting the maximum total value.
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 2005
#define ll long long
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
struct node{
ll sum,lsum,rsum,msum;
}tr[maxn<<];
struct ww{
ll x,y,val;
bool operator <(const ww &w)const{
if(y==w.y)return x<w.x;
return y<w.y;
}
}a[maxn];
inline void pushup(int rt)
{
tr[rt].sum=tr[rt<<].sum+tr[rt<<|].sum;
tr[rt].lsum=max(tr[rt<<].lsum,tr[rt<<].sum+tr[rt<<|].lsum);
tr[rt].rsum=max(tr[rt<<|].rsum,tr[rt<<|].sum+tr[rt<<].rsum);
tr[rt].msum=max(max(tr[rt<<].msum,tr[rt<<|].msum),tr[rt<<|].lsum+tr[rt<<].rsum);
}
inline void build(int l,int r,int rt)
{
if(l==r)
{
tr[rt].sum=tr[rt].msum=tr[rt].lsum=tr[rt].rsum=;
return ;
}
int mid=l+r>>;
build(ls);build(rs);
pushup(rt);
}
inline void update(int L,int c,int l,int r,int rt)
{
if(l==r)
{
tr[rt].sum=tr[rt].msum=tr[rt].lsum=tr[rt].rsum+=1ll*c;
return ;
}
int mid=l+r>>;
if(L<=mid)update(L,c,ls);
else update(L,c,rs);
pushup(rt);
}
ll x[maxn],y[maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=;i<=n;i++)
{
cin>>a[i].x>>a[i].y>>a[i].val;
x[i]=a[i].x;y[i]=a[i].y;
}
sort(x+,x++n);
sort(y+,y++n);
int lenx=unique(x+,x++n)-x-;
int leny=unique(y+,y++n)-y-;
for(int i=;i<=n;i++)
{
a[i].x=lower_bound(x+,x++lenx,a[i].x)-x;
a[i].y=lower_bound(y+,y++leny,a[i].y)-y;
}
sort(a+,a++n);
ll ans=;
for(int i=;i<=leny;i++)//确定矩形下边界
{
build(,lenx,);
int pos=;
while(a[pos].y<i)pos++;
for(int j=i;j<=leny;j++)//确定矩形上边界
{
for(;a[pos].y==j;pos++)//插入纵坐标相同的点
{
update(a[pos].x,a[pos].val,,lenx,);
}
ans=max(ans,tr[].msum);//更新答案
}
}
cout<<ans<<endl;
}
return ;
}
最新文章
- 潭州学院-JavaVIP的Javascript的高级进阶-KeKe老师
- FineUI(专业版)实现百变通知框(无JavaScript代码)!
- Windows Phone中扩展WebBrowser使其支持绑定html内容
- UESTC 914 方老师的分身I Dijkstra
- 用C语言简单加密解密
- codevs2622数字序列( 连续子序列最大和O(n)算法)
- js获取当前url参数的两方式
- C# WebBrowser 代理的使用
- window.location.href 和 document.location.href
- Java中ArrayList与LinkedList的区别
- JavaScript 变量、类型与计算
- Android Multimedia框架总结(六)C++中MediaPlayer的C/S架构
- 团队项目——NABCD
- 面试必备:ArrayList源码解析(JDK8)
- MySQL命令,一篇文章替你全部搞定
- vue基础篇---watch监听
- addEventListener在一个节点上添加多个相同的事件
- c#调用刀片小票打印机
- Ubuntu Linux系统三种方法添加本地软件库
- AppScan扫描建议 问题集