bzoj2131: 免费的馅饼（树状数组）

Description

Input

第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到10^8之间）和馅饼的个数n（1到10^5）。　　接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。

Output

一个数，表示游戏者获得的最大总得分。

Sample Input

3 4
1 2 3
5 2 3
6 3 4
1 1 5

Sample Output

12
【数据规模】
对于100%的数据，1<=w,t[i]<=10^8,1<=n<=100000。

首先不难得到转移方程$dp[i]=max\{dp[j]\}+val[i](|p_i-p_j|\leq 2t_i-2t_j)$

考虑怎么转换限制条件，$p_i-p_j\leq 2t_i-2t_j$且$p_j-p_i\leq 2t_i-2t_j$，则有$2t_i-p_i\geq 2t_j-p_j$且$2t_i+p_i\geq 2t_j+p_j$

那么就是一个二维偏序问题了，先排序消除第一维的影响，然后用树状数组维护第二维就好了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 ll read(){

     #define num ch-'0'

     char ch;bool flag=;ll res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=5e5+;

 int n,w;ll c[N];

 inline void add(int x,ll y){

     for(;x<=n+;x+=x&-x) cmax(c[x],y);

 }

 ll query(int x){

     ll res=;for(;x;x-=x&-x) cmax(res,c[x]);return res;

 }

 struct node{

     int x,y;ll v;

     inline bool operator <(const node &b)const

     {return x==b.x?y<b.y:x<b.x;}

 }a[N];int b[N];

 int main(){

 //    freopen("testdata.in","r",stdin);

     w=read(),n=read();

     for(int i=;i<=n;++i){

         int t=read(),p=read();a[i].v=read();

         a[i].x=*t+p,a[i].y=*t-p,b[i]=a[i].y;

     }

     sort(a+,a++n),sort(b+,b+n+);

     for(int i=;i<=n;++i){

         ll res=;int pos=lower_bound(b+,b++n,a[i].y)-b;

         res=query(pos)+a[i].v,add(pos,res);

     }

     printf("%lld\n",query(n+));

     return ;

 }

巴特西