题目链接:https://darkbzoj.tk/problem/2131
题意:有 个从天而降的馅饼,会告诉你每个馅饼掉落的地点时间以及馅饼的价值,刚开始你可以站在任意一个位置,之后你每秒可以向左或向右移动 个或 个单位,也可以不动,问能获得的最大价值。
思路:我们考虑两个馅饼 , ,它们都可以用一个三元组表示 , ,假设 根据题意我们可以列出这么一个表达式
我们拆掉绝对值然后移一下项可以得到以下式子
所以我们做一下坐标变换,发现这就是经典的带权 问题,树状数组优化 即可,时间复杂度 。
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
x=0;int f=0;char ch=getchar();
while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x=f?-x:x;
}
const int N=1e5+10;
struct Node{
int x,y,v;
bool operator<(const Node&rhs)const{
if (x==rhs.x) return y>rhs.y;
return x<rhs.x;
}
}coin[N];
int w,n,m,i,p,t,v,ans,dp[N],mx[N];
vector<int>vec;
void compress(){
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for (i=1;i<=n;++i){
int pos=lower_bound(vec.begin(),vec.end(),coin[i].y)-vec.begin();
coin[i].y=pos+1;
}
m=(int)vec.size();
}
inline int lowbit(int x){return x&(-x);}
void update(int x,int p){for (;x<=m;x+=lowbit(x)) mx[x]=max(mx[x],p);}
int query(int x){
int ret=0;
for (;x>0;x-=lowbit(x)) ret=max(ret,mx[x]);
return ret;
}
int main(){
read(w),read(n);
for (i=1;i<=n;++i){
read(t),read(p),read(v);
coin[i].x=2*t+p;
coin[i].y=2*t-p;
coin[i].v=v;
vec.PB(coin[i].y);
}
compress();
sort(coin+1,coin+1+n);
for (i=1;i<=n;++i){
dp[i]=query(coin[i].y)+coin[i].v;
ans=max(ans,dp[i]);
update(coin[i].y,dp[i]);
}
printf("%d\n",ans);
return 0;
}
Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github
Cannot load comments. Please check you network.