RUPC 2014 day3 F : Dangerous Delivery

問題

要約不能なので元の問題文参照(http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp14Day3&pid=F


数直線上にn個の点が左から順に並んでいて、
1番の点からn番の点まで、D回以下の移動で移動したい。


一回の移動ではi->jの好きな点に移動できるが、
(その時点で点iを監視しているきゅうりの数)× abs(p[j] - p[i])のコストがかかる。


全てのきゅうりは一様に右向きに速度xで移動していて、
自分が点から点への移動を一回行うごとに、きゅうりは右にx移動して、監視する点が増える。

制約条件

n≦10^4
d≦10^2

方針

dp[i回移動した][j番の点にいる] := このときの最小コスト
を更新するDP.
そのままだとO(dn^2)かかってTLE.


だけどこれはi回目の移動についてみたとき、
凸法DP(蟻本のエンベロープDP)そのまんまのやり方で、
(i回目の移動の)n個の更新がO(n)でできる。


全体の計算量はO(dn)に落ちる。


エンベロープDPは、直線の下側の部分を求めるやつで、
これは追加されていく直線の傾きが単調減少になっているので、デックを使って線形の計算量でできるパターン。

ソースコード

const int N = 10010;

int n, m, d, x;
int p[N];
ll dp[2][N];

vi pos;

inline ll watcher(int i, int idx){
	return m - (lower_bound(all(pos), p[idx] - i * x) - pos.begin());
}

bool check(int i, int f1, int f2, int f3){
	
	ll a1 = watcher(i, f1), b1 = dp[i%2][f1] - watcher(i, f1) * p[f1];
	ll a2 = watcher(i, f2), b2 = dp[i%2][f2] - watcher(i, f2) * p[f2];
	ll a3 = watcher(i, f3), b3 = dp[i%2][f3] - watcher(i, f3) * p[f3];
	
	return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);
}
bool check2(int i, int f1, int f2, int j){
	
	ll a = dp[i%2][f1] + watcher(i, f1) * (p[j] - p[f1]);
	ll b = dp[i%2][f2] + watcher(i, f2) * (p[j] - p[f2]);
	
	return a >= b;
}

int main(){
	
	cin >> n >> m >> d >> x;
	rep(i, n) cin >> p[i];
	
	rep(i, m){
		int a, b;
		cin >> a >> b;
		
		pos.pb(a - abs(b));
	}
	sort(all(pos));
	
	
	rep(i, n) dp[0][i] = (ll)1e12;
	dp[0][0] = 0;
	
	int cur = 0, next = 1;
	
	rep(i, d){
		deque<int> q;
		
		rep(j, n){
			while(q.size() > 1 && check2(i, q[0], q[1], j)) q.pop_front();
			
			dp[next][j] = dp[cur][j];
			if(q.size()) dp[next][j] = min(dp[next][j],
			dp[cur][q[0]] + watcher(i, q[0]) * (p[j] - p[q[0]]));
			
			while(q.size() > 1 && check(i, q[q.size() - 2], q[q.size() - 1], j)) q.pop_back();
			q.pb(j);
		}
		swap(cur, next);
	}
	
	cout << dp[cur][n - 1] << endl;
	
	return 0;
}