牛客练习赛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; }

总结

以上是生活随笔为你收集整理的牛客练习赛59 小松鼠吃松果(优化dp二维偏序)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。