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