bzoj 2131 免费的馅饼

Written with StackEdit.

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

HINT

对于(100\%)的数据，(1<=w,t[i]<=10^8,1<=n<=100000.)

Solution

比较明显的朴素(dp)思路是,设(f[i])表示最后拿的一个饼是第(i)个的最大收益.
显然有(f[i]=max){(f[j]|j<i,|p[i]-p[j]|leq 2(t[i]-t[j]))}(+v[i]).
这样是(O(n^2))的,需要优化.
我们将限制条件中的绝对值式子拆开,得到两个不等式.
- (2t[i]+p[i]geq 2t[j]+p[j].)
- (2t[i]-p[i]geq 2t[j]-p[j].)
那么我们将(2t+p,2t-p)视作两维,先按照一维排序,再对另一维离散化,利用树状数组优化转移.
(j<i)的条件此时可以直接忽略掉,因为(f[i])现在表示某一维的值对应的最优解,不再与时间联系.

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
const int inf=1e9;
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e5+10;
struct pies{
	int t,p,v;//落地时间,落地位置,价值 
	int a,b;//b存储离散化后的值 
	// a = 2*t + p
	// b = 2*t - p 
	bool operator < (const pies &rhs) const {
		return a<rhs.a;
	}
}x[MAXN];
struct unipies{
	int b,id;
	bool operator < (const unipies &rhs) const {
		return b<rhs.b;
	}
}y[MAXN];
int n,w;
int unin=0;
int f[MAXN];
//f[i]=f[j]+v[i], j<i && abs(p[i]-p[j])<=2*(t[i]-t[j])
void Unique()
{
	sort(y+1,y+1+n);
	y[0].b=-inf;
	for(int i=1;i<=n;++i)
		{
			if(y[i].b!=y[i-1].b)
				++unin;
			x[y[i].id].b=unin;
		}
}
int bit[MAXN];
inline void upd(int x,int c)
{
	for(;x<=unin;x+=lowbit(x))
		bit[x]=max(bit[x],c);
}
inline int query(int x)
{
	int res=-inf;
	for(;x;x-=lowbit(x))
		res=max(res,bit[x]);
	return res;
}
int main()
{
	w=read(),n=read();
	for(int i=1;i<=n;++i)
		{
			x[i].t=read();
			x[i].p=read();
			x[i].v=read();
			x[i].a=x[i].t*2+x[i].p;
			y[i].b=x[i].t*2-x[i].p;
			y[i].id=i;
		}
	Unique();
	sort(x+1,x+1+n);
	for(int i=1;i<=n;++i)
		{
			int newv=query(x[i].b)+x[i].v;
			upd(x[i].b,newv);
		}
	int ans=query(unin);
	printf("%d
",ans);
	return 0;
}

参考了dalao的blog.