题意分析
记原题面中 $n,H_i,P_i,C_i$ 分别为 $n,h_i,p_i,c_i$。
考虑 DP 求解最大收益，不难发现最终有效的 $h_i$ 一定是先上升在下降的。
对于这种「单峰」的东西，DP 可以考虑做两次：上升和下降，即从前往后 $h_i$ 不降和从前往后 $h_i$ 不增。
以 $h_i$ 不降为例，设 $\textit{dp}_{i,j}$ 表示 $1\sim i$，有效的 $h_i$ 最大值为 $j$ 的时候的最大收益。
$h$ 显然可以离散化。
考虑：
-
$h_i$ 有贡献，那么：
\[\textit{dp}_{i,h_i}=\max_{j=1}^{h_i}\textit{dp}_{i-1,j}+p_i\] -
$h_i$ 没有贡献。因为收益最大，因此被挡住的时候不应该拔掉：
- $h_i$ 被挡住，即 $h_i<j$，有 $\textit{dp}{i,j}=\textit{dp}{i-1,j}$。
- $h_i$ 被拔掉，即 $j<h_i$，有 $\textit{dp}{i,j}=\textit{dp}{i-1,j}-c_i$。
可以发现这是一个 $\mathcal O\left(n^2\right)$ 的 DP，可以得到 $\text{30pts}$。
又可以发现 $i$ 这一维的信息仅与 $i-1$ 有关，这一维可以直接砍掉。
如何优化呢？DP 式中很多修改都是相同的，即对于 $j<h_i$，减去 $c_i$；对于 $j=h_i$，前缀 $\max$ 维护；对于 $j>h_i$ 不变。
容易想到线段树优化 DP，区间减去 $c_i$、求前缀 $\max$、单点修改即可。
时间复杂度 $\mathcal O(n\log n)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
#define int long long
constexpr const int N=1e5;
int n,m,h[N+1],p[N+1],c[N+1];
int pre[N+1],suf[N+1];
void discrete(){
static int tmp[N+1];
for(int i=1;i<=n;i++){
tmp[i]=h[i];
}
sort(tmp+1,tmp+n+1);
m=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=n;i++){
h[i]=lower_bound(tmp+1,tmp+m+1,h[i])-tmp;
}
}
struct segTree{
struct node{
int l,r;
int max,tag;
int size(){
return r-l+1;
}
}t[N<<2|1];
void up(int p){
t[p].max=::max(t[p<<1].max,t[p<<1|1].max);
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r){
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void down(int p){
if(t[p].tag){
t[p<<1].max+=t[p].tag;
t[p<<1].tag+=t[p].tag;
t[p<<1|1].max+=t[p].tag;
t[p<<1|1].tag+=t[p].tag;
t[p].tag=0;
}
}
void add(int p,int l,int r,int x){
if(r<l){
return;
}
if(l<=t[p].l&&t[p].r<=r){
t[p].max+=x;
t[p].tag+=x;
return;
}
down(p);
if(l<=t[p<<1].r){
add(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
add(p<<1|1,l,r,x);
}
up(p);
}
void chkmax(int p,int x,int k){
if(t[p].l==t[p].r){
t[p].max=::max(t[p].max,k);
return;
}
down(p);
if(x<=t[p<<1].r){
chkmax(p<<1,x,k);
}else{
chkmax(p<<1|1,x,k);
}
up(p);
}
int max(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].max;
}
down(p);
int ans=-2147483647;
if(l<=t[p<<1].r){
ans=max(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::max(ans,max(p<<1|1,l,r));
}
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i]>>p[i]>>c[i];
}
discrete();
t.build(1,1,m);
for(int i=1;i<=n;i++){
pre[i]=t.max(1,1,h[i])+p[i];
t.add(1,1,h[i]-1,-c[i]);
t.chkmax(1,h[i],pre[i]);
}
t.build(1,1,m);
for(int i=n;1<=i;i--){
suf[i]=t.max(1,1,h[i])+p[i];
t.add(1,1,h[i]-1,-c[i]);
t.chkmax(1,h[i],suf[i]);
}
int ans=pre[1]+suf[1]-p[1];
for(int i=2;i<=n;i++){
ans=max(ans,pre[i]+suf[i]-p[i]);
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
