LOJ2396 JOISC2017 长途巴士 斜率优化

时间：2022-03-25 01:01:37

传送门

将乘客按照\(D_i\)从小到大排序并重新标号。对于服务站\(j\)，如果\(S_j \mod T \in (D_i , D_{i+1})\)，那么可以少接一些水，在保证司机有水喝的情况下让编号在\([x,i](x \in [1,i])\)的乘客下车（我们将这个区间称作这个服务区的下车区间），然后到达这个服务站接水。区间\([D_x , D_i]\)之间有服务区也没关系，只要在服务区不接水就可以了。

所以有DP：设\(f_i\)表示考虑了前\(i\)个乘客，最少花费的费用是多少。转移有：①\(f_i = f_{i-1} + \lfloor \frac{X - D_i}{T} \rfloor \times W\)，表示第\(i\)个人一直坐到终点；②如果在\((D_i , D_{i+1})\)内有服务站，还有转移\(f_i = \min\limits_{0 \leq j < i} f_j + (i - j) \times W \times cnt + \sum\limits_{k = j + 1}^i C_k\)，其中\(cnt\)表示的是\(j+1\)到\(i\)的乘客的最少饮水次数，也就是\(\min\limits_{S_k \mod T \in (D_i , D_{i+1})}\lfloor \frac{S_k}{T} \rfloor\)

对于一些乘客，如果我们已经确定了他们要下车，那么一定是越早下车越好，也就是说所有服务站的下车区间一定无交，所以上面②的转移是正确的。

把\(\sum\limits_{k = j + 1}^i C_k\)变成前缀和，就是一个可以斜率优化的式子，栈维护凸包即可。

#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

#define INF 1e18

//This code is written by Itst

using namespace std;

#define int long long

inline int read(){

	int a = 0;

	char c = getchar();

	while(!isdigit(c))

		c = getchar();

	while(isdigit(c)){

		a = a * 10 + c - 48;

		c = getchar();

	}

	return a;

}

#define PII pair < int , int >

#define st first

#define nd second

const int MAXN = 2e5 + 3;

int N , M , X , W , T , top = 1;

int dp[MAXN] , dis[MAXN] , stk[MAXN];

struct machine{

	int D , C;

	bool operator <(const machine a)const{return D < a.D;}

}now[MAXN];

long double calc(PII A , PII B){

	return 1.0 * (A.nd - B.nd) / (B.st - A.st);

}

PII create(int x){return PII(-x * W , dp[x] - now[x].C);}

bool chk(int a , int b , int c){

	PII A = create(a) , B = create(b) , C = create(c);

	return calc(A , B) > calc(A , C);

}

int calc(PII a , int x){return a.st * x + a.nd;}

int get(int X){

	int L = 1 , R = top;

	while(L < R){

		int mid = (L + R) >> 1;

		calc(create(stk[mid]) , X) > calc(create(stk[mid + 1]) , X) ? L = mid + 1 : R = mid;

	}

	return calc(create(stk[L]) , X);

}

bool cmp(int a , int b){return a % T < b % T;}

signed main(){

#ifndef ONLINE_JUDGE

	freopen("eternity.in","r",stdin);

	freopen("eternity.out","w",stdout);

#endif

	X = read(); N = read(); M = read(); W = read(); T = read();

	for(int i = 1 ; i <= N ; ++i)

		dis[i] = read();

	dis[++N] = X;

	for(int i = 1 ; i <= M ; ++i){

		now[i].D = read();

		now[i].C = read();

	}

	sort(dis + 1 , dis + N + 1 , cmp);

	sort(now + 1 , now + M + 1);

	now[M + 1].D = T;

	for(int i = 1 ; i <= M ; ++i)

		now[i].C = now[i].C + now[i - 1].C;

	memset(dp , 0x3f , sizeof(dp));

	dp[0] = 0; int pos = 1;

	while(pos <= N && dis[pos] % T <= now[1].D) ++pos;

	for(int i = 1 ; i <= M ; ++i){

		int Min = INF;

		while(pos <= N && dis[pos] % T < now[i + 1].D)

			Min = min(Min , dis[pos++] / T);

		dp[i] = dp[i - 1] + ((X - now[i].D) / T + 1) * W;

		if(Min != INF)

			dp[i] = min(dp[i] , get(Min) + Min * W * i + now[i].C);

		while(top > 1 && chk(stk[top - 1] , stk[top] , i))

			--top;

		stk[++top] = i;

	}

	cout << dp[M] + (X / T + 1) * W;

	return 0;

}

相关文章