线段树优化dp——牛客多校第一场I(好题)
2024-10-07 20:16:25
和两天做了两道数据结构优化dp的题,套路还是差不多的
题解链接! https://www.cnblogs.com/kls123/p/11221471.html
一些补充
其实这道题的dp[i]维护的不是每个点,而是每个离散化的y,也可以理解为当前折线停留在纵坐标为y的答案
从左往右,从上往下进行遍历点,对于每个点p[i]考虑三种情况:
1.折线经过这个点,那么这条折线必定从小于等于p[i].y的地方折上来的,所以查询一段区间的极值即可
2.折线在这个点上面,那么通过这个点去更新那些在其上面的折线值即可
3.折线在点下面,和2同理
此外,由于折线可能是直接从y=0折上来的,所以必须增加y=0的点来进行第1种转移,不加是错误的,等于少了这种情况!
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid ll m = (l + r) >> 1 const int M = 1e5+;
ll mx[M<<],lazy[M<<];
void up(ll rt){
mx[rt] = max(mx[rt<<],mx[rt<<|]);
} void pushdown(ll rt){
if(lazy[rt]){
lazy[rt<<] += lazy[rt];
lazy[rt<<|] += lazy[rt];
mx[rt<<] += lazy[rt];
mx[rt<<|] += lazy[rt];
lazy[rt] = ;
}
} void build(ll l,ll r,ll rt){
lazy[rt] = ; mx[rt] = ;
if(l == r){
return ;
}
mid;
build(lson); build(rson);
} void update(ll p,ll c,ll l,ll r,ll rt){
if(l == r){
mx[rt] = max(mx[rt],c);
return ;
}
pushdown(rt);
mid;
if(p <= m) update(p,c,lson);
else update(p,c,rson);
up(rt);
} void update1(ll L,ll R,ll c,ll l,ll r,ll rt){
if(L > R) return ; //会出现L > R的情况,需要判下
if(L <= l&&R >= r){
mx[rt] += c;
lazy[rt] += c;
return ;
}
pushdown(rt);
mid;
if(L <= m) update1(L,R,c,lson);
if(R > m) update1(L,R,c,rson);
up(rt);
} ll query(ll L,ll R,ll l,ll r,ll rt){
if(L > R) return ;
if(L <= l&&R >= r){
return mx[rt];
}
pushdown(rt);
mid;
ll ret = ;
if(L <= m) ret = max(ret,query(L,R,lson));
if(R > m) ret = max(ret,query(L,R,rson));
return ret;
} struct node{
ll x,y,a,b;
}v[M];
bool cmp(node aa,node bb){
if(aa.x == bb.x) return aa.y > bb.y;
return aa.x < bb.x;
}
ll t[M];
int main()
{
ll n;
while(scanf("%lld",&n)!=EOF){
ll cnt = ;
for(ll i = ;i <= n;i ++){
scanf("%lld%lld%lld%lld",&v[i].x,&v[i].y,&v[i].a,&v[i].b);
t[++cnt] = v[i].y;
}
sort(t+,t++cnt);
sort(v+,v++n,cmp);
ll m = unique(t+,t++cnt)-t-;
for(ll i = ;i <= n;i ++)
v[i].y = lower_bound(t+,t++m,v[i].y)-t+; //离散化时点都向后移一位
m ++; //点后移了一位,长度要+1;
build(,m,);
for(ll i = ;i <= n;i ++){
ll ans = query(,v[i].y,,m,);
update1(v[i].y+,m,v[i].b,,m,);
update1(,v[i].y-,v[i].a,,m,);
update(v[i].y,ans+v[i].b,,m,);
}
printf("%lld\n",mx[]);
}
return ;
}
最新文章
- 【笔记】js清空cookie
- clone()与clone(true)的区别
- 项目SVN的IP地址发生变化时修改SVN为新的IP地址
- Django Tutorial 学习笔记
- 关于python文件转为exe文件
- 【错误总结之(一)】error LNK2038: 检測到“_ITERATOR_DEBUG_LEVEL”的不匹配项: 值“0”不匹配值“2”
- ultravnc
- PHP 3:从Login界面谈PHP标记
- 《深入理解Bootstrap》读书笔记(一)
- LINQ 详解
- ES6中const、let与var的对比详解
- IntelliJ IDEA常用快捷键(Mac)
- android 测试
- HashSet源码
- Java 8 Lambda实现原理分析
- python3中文转码方法
- MFC+WinPcap编写一个嗅探器之三(WinPcap)
- 【BZOJ】4767: 两双手【组合数学】【容斥】【DP】
- Nginx启用ssl以及免费证书申请
- spring 启动过程