PerfectPan
;

BZOJ 2131 免费的馅饼

February 03, 2019

题目链接https://darkbzoj.tk/problem/2131

题意:有 nn 个从天而降的馅饼,会告诉你每个馅饼掉落的地点时间以及馅饼的价值,刚开始你可以站在任意一个位置,之后你每秒可以向左或向右移动 11 个或 22 个单位,也可以不动,问能获得的最大价值。

思路:我们考虑两个馅饼 ii, jj,它们都可以用一个三元组表示 (ti,posi,vali)(t_i,pos_i,val_i), (tj,posj,valj)(t_j,pos_j,val_j),假设 tj>tit_j>t_i 根据题意我们可以列出这么一个表达式

posiposj2tj2ti|pos_i-pos_j|\le 2t_j-2t_i

我们拆掉绝对值然后移一下项可以得到以下式子

2ti+posi2tj+posj2tiposi2tjposj.\begin{matrix}2t_i+pos_i\le 2t_j+pos_j\\2t_i-pos_i\le 2t_j-pos_j\end{matrix}.

所以我们做一下坐标变换,发现这就是经典的带权 LISLIS 问题,树状数组优化 DPDP 即可,时间复杂度 O(nlogn)O(nlogn)

#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;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.