由于未知不稳定因素,在某些评测机上可能有锅,欢迎指正:
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct data{
int t,p,v;
int fir,sec;
void push(){
scanf("%d%d%d",&t,&p,&v);
t<<=1;
}
int count(){
fir=t+p;
sec=t-p;
}
}d[maxn];
bool cmp1(data x,data y){return x.fir<y.fir;}
bool cmp2(data x,data y){return x.sec<y.sec;}
int t[maxn];
int f[maxn];
int c[maxn];
int n;
inline int mymax(int x,int y){return x>y?x:y;}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int num){
for(int i=x;i<=n;i+=lowbit(i))c[i]=mymax(c[i],num);
}
inline int ask(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res=mymax(c[i],res);
return res;
}
int main(){
int w;
scanf("%d%d",&w,&n);
for(int i=1;i<=n;i++){
d[i].push();
d[i].count();
}
sort(d+1,d+1+n,cmp1);
int tot=0;
for(int i=1;i<=n;i++)
if(d[i].fir!=d[i-1].fir)
d[i].fir=++tot;
sort(d+1,d+1+n,cmp2);
int ans=0;
for(int i=1;i<=n;i++){
f[i]=ask(d[i].fir)+d[i].v;
ans=mymax(ans,f[i]);
add(d[i].fir,f[i]);
}
printf("%d\n",ans);
return 0;
}
数据结构优化的DP太难了(T…T)