bzoj 2131 免费的馅饼

Description

bzoj 2131 免费的馅饼-LMLPHP

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\n",ans);

	return 0;

}

参考了dalao的blog.

2t