牛客练习赛59 小松鼠吃松果(优化dp二维偏序)

小松鼠吃松果

非常$nice$的一道题

首先考虑$dp$

容易想到按照时间来排序

然后定义$dp[i]$为考虑前$i$个果子且吃掉第$i$个的最大价值

那么每次都去前面枚举一个$j$使得吃完$j$还可以来吃$i$

吃完$j$还能吃$i$有什么条件呢??

$$t_i-t_j>=abs(po{s}_i-po{s}_j)$$

$当po{s}_i>=po{s}_j,t_i-po{s}_i>=t_j-po{s}_j$

$当po{s}_i<po{s}_j,t_i+po{s}_i>=t_j+po{s}_j$

用树状数组维护即可

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2e5+10; int pos[maxn],b[maxn],ls[maxn],sumn[maxn],n,m; struct node{ int t,id,val; bool operator < (const node&tmp ) const{ return t==tmp.t?id<tmp.id:t<tmp.t;//优先按照x来排序 } }a[maxn]; int lowbit(int x){ return x&(-x); } int query(int x) { int ans=0; for(;x;x-=lowbit(x)) ans = max( ans,sumn[x] ); return ans; } void add(int x,int v) { for(;x<=n;x+=lowbit(x)) sumn[x]=max(sumn[x],v); } signed main() { cin >> n >> m; for(int i=1;i<=m;i++) scanf("%d",&pos[i]),ls[i]=pos[i]; for(int i=1;i<=m;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].t,&a[i].id,&a[i].val),a[i].t+=b[a[i].id]; for(int i=1;i<=n;i++) { int x=a[i].t-pos[a[i].id],y=a[i].t+pos[a[i].id]; a[i].t=x,a[i].id=y; ls[i]=y; } sort(ls+1,ls+1+n); sort(a+1,a+1+n); int ans=0; for(int i=1;i<=n;i++) { int now=lower_bound(ls+1,ls+1+n,a[i].id)-ls; int dp=query(now)+a[i].val; ans = max( ans,dp ); add( now,dp ); } cout << ans; }