P5902 [IOI2009] salesman 题解

标签：P5902 return int 题解 long res salesman define

题目链接

题意

船向上游移动 1 米花费 \(U\) 元，向下移动 1 米花费 \(D\) 元。

沿河有 \(N\) 个展销会，对于第 \(i\) 个展销会，它的日期为 \(T_i\)，它的位置为 \(L_i\)，可获得盈利 \(M_i\) 元。

一个需要从位置 \(S\) 开始和结束他的旅程。

求它能得到的最大盈利。

题解

直接暴力是 \(O(N^3)\) 的。

一开始先排序一下。设 \(f(i)\) 表示前 \(i\) 个展销会，终点是 \(i\)。

如果不考虑同一天，那么只要枚举转移时从哪一天：

\[f(i)=\max_{j=0}^i\{f(j)-(L_i-L_j)\cdot U\}+w_i \]

还有一种往下走的要考虑。

代码

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rept(i,n) for(int i=1;i<=n;i++)
#define repe(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define fi first
#define se second
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define sz(v) (int)(v.size())
using namespace std;
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template<typename T>void chmax(T& a,T b){if(a<b)a=b;return;}
template<typename T>void chmin(T& a,T b){if(a>b)a=b;return;}
const int N=5e5+10;
int n,u,d,s,dp[N],tol[N],tor[N];
struct node{
	int t,l,w;
	bool operator<(const node &x)const{
		if(t!=x.t){
			return t<x.t;
		}
		return l<x.l;
	}
}a[N];
int tree1[N],tree2[N];
int lowbit(int x){
	return x&(-x);
}
void update1(int x,int v){
	while(x<N){
		chmax(tree1[x],v);
		x+=lowbit(x);
	}
}
int query1(int x){
	int res=-0x3f3f3f3f3f3f3f3f;
	while(x>0){
		chmax(res,tree1[x]);
		x-=lowbit(x);
	}
	return res;
}
void update2(int x,int v){
	while(x>0){
		chmax(tree2[x],v);
		x-=lowbit(x);
	}
}
int query2(int x){
	int res=-0x3f3f3f3f3f3f3f3f;
	while(x<N){
		chmax(res,tree2[x]);
		x+=lowbit(x);
	}
	return res;
}
void solve(int l,int r){
	repe(i,l,r){
		tol[i]=tor[i]=max(query1(a[i].l)-a[i].l*d,query2(a[i].l)+a[i].l*u)+a[i].w;
	}
	repe(i,l+1,r){
		chmax(tol[i],tol[i-1]-(a[i].l-a[i-1].l)*d+a[i].w);
	}
	FOR(i,r-1,l){
		chmax(tor[i],tor[i+1]-(a[i+1].l-a[i].l)*u+a[i].w);
	}
	repe(i,l,r){
		dp[i]=max(tol[i],tor[i]);
		update1(a[i].l,dp[i]+a[i].l*d);
		update2(a[i].l,dp[i]-a[i].l*u);
	}
}
signed main(){
	memset(tree1,-0x3f,sizeof(tree1));
	memset(tree2,-0x3f,sizeof(tree2));
	memset(dp,-0x3f,sizeof(dp));
	scanf("%lld%lld%lld%lld",&n,&u,&d,&s);
	rept(i,n){
		scanf("%lld%lld%lld",&a[i].t,&a[i].l,&a[i].w);
	}
	a[n+1].t=0x3f3f3f3f3f3f3f3f;
	a[0].l=a[n+1].l=s;
	sort(a+1,a+1+n);
	dp[0]=0;
	update1(s,s*d);
	update2(s,-s*u);
	rept(i,n+1){
		if(a[i].t==a[i+1].t){
			int tmp=i;
			while(a[i].t==a[i+1].t){
				i++;
			}
			solve(tmp,i);
			continue;
		}
		dp[i]=max(query1(a[i].l)-a[i].l*d,query2(a[i].l)+a[i].l*u)+a[i].w;
		update1(a[i].l,dp[i]+a[i].l*d);
		update2(a[i].l,dp[i]-a[i].l*u);
	}
	printf("%lld\n",dp[n+1]);
	return 0;
}
//Jerry_Jiang

标签：P5902,return,int,题解,long,res,salesman,define
From： https://www.cnblogs.com/Jerry-Jiang/p/P5902.html