显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
const int SIZEN=100010;
int N,W;
int f[SIZEN]={0};
class BIT{//树状数组,存放前缀最大值
public:
int n;
int s[SIZEN];
#define lowbit(x) (x)&(-x)
void clear(int n_){n=n_;memset(s,0,sizeof(s));}
void change(int x,int t){
for(;x<=n;x+=lowbit(x)) s[x]=max(s[x],t);
}
int query(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans=max(ans,s[x]);
return ans;
}
}T;
/*
以p为横轴,t为纵轴,那么新坐标的基向量是(1,1)和(-1,1)
一个点能由新坐标系中左下方的那些点转移而来
*/
class PIE{
public:
int t,p,v;
int x,y;
void printtc(void){printf("(%d %d)",x,y);}
};
void print(PIE s){s.printtc();cout<<" "<<s.v;}
bool cmp_yx(PIE a,PIE b){
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
PIE S[SIZEN];
void work(void){
int ans=0;
T.clear(N+1);
sort(S,S+N+1,cmp_yx);
T.change(S[0].x,f[0]=0);//充满仪式感的赋值,尽管没用......
for(int i=1;i<=N;i++){
f[i]=S[i].v+T.query(S[i].x);
ans=max(ans,f[i]);
T.change(S[i].x,f[i]);
}
printf("%d\n",ans);
}
map<int,int> X;
void discretize(void){//我们扫描y轴,因此只需要离散化x轴
for(int i=0;i<=N;i++) X[S[i].x]=0;
int tot=0;
for(map<int,int>::iterator key=X.begin();key!=X.end();key++) key->second=++tot;
for(int i=0;i<=N;i++) S[i].x=X[S[i].x];
}
void read(void){
scanf("%d%d",&W,&N);
S[0].t=-W,S[0].p=0;//既然可以从任意一格开始,那就提前开始让人自己跑算了
for(int i=1;i<=N;i++){
scanf("%d%d%d",&S[i].t,&S[i].p,&S[i].v);
S[i].t*=2;//每秒钟走一格
}
for(int i=0;i<=N;i++) S[i].x=(S[i].t+S[i].p),S[i].y=(S[i].t-S[i].p);
}
int main(){
freopen("free.in","r",stdin);
freopen("free.out","w",stdout);
read();
discretize();
work();
return 0;
}
cstdio