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
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.