8VC Venture Cup 2016 - Final Round C. Package Delivery
これはいろいろ難しい問題でした… 良い問題だと思います。
解法
まず方針です。なんとなく貪欲な気がしますが, 気づくのが難しいです。
next[i] = (x[i] から n 以内で進める場所にあって, p[i] よりもコストが小さい, 最もx[i] に近い座標) を求めます。next[i] は存在しない可能性もあります。その時は next[i] = -1 にしておきましょう。この時,
- next[i] が存在する場合
- next[i] にいける最低限の燃料だけ補充し, next[i] に向かう
- next[i] が存在しない場合
- x[i] で燃料を満タンにして先に進む
という戦略が最適です。まぁ言われればアタリマエですね。
で, あと問題になるのは, next[i] を高速で求める方法です。これには stack が使えます。下の問題に似た感じです(n 回目)。
mayokoex.hatenablog.com
const int MAXM = 200200; const int INF = 1e9+7; pii P[MAXM]; int main() { cin.tie(0); ios::sync_with_stdio(false); int d, n, m; cin >> d >> n >> m; P[0] = pii(0, INF); P[m+1] = pii(d, 0); for (int i = 1; i <= m; i++) cin >> P[i].first >> P[i].second; m += 2; sort(P, P+m); vector<int> next(m, -1); stack<int> st; for (int i = 0; i < m; i++) { while (!st.empty()) { int index = st.top(); if (P[index].second <= P[i].second || P[index].first+n < P[i].first) break; next[index] = i; st.pop(); } st.push(i); } ll ans = 0; int now = n; for (int i = 0; i < m-1; i++) { if (P[i+1].first - P[i].first > n) { cout << -1 << endl; return 0; } if (next[i] == -1) { ans += (ll)(n-now) * P[i].second; now = n; } else { int need = P[next[i]].first-P[i].first; if (now < need) { ans += (ll)(need-now) * P[i].second; now = need; } } now -= P[i+1].first-P[i].first; } cout << ans << endl; return 0; }