AtCoder ABC 320 F - Fuel Round Trip (黄色, 550 点)

少し重たかった。でもいい問題。JOI にありそう。

• 問題へのリンク

問題概要

数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。

• 座標 にある
• 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う)

今、高橋君は座標 を HP が である状態で出発して、座標 の地点を訪れて、座標 の地点へと引き返す。なお、1 進むと HP が 1 減少する。

注意したいこととして、どの補給所も高々 1 回しか使えない。つまり、行きの途中で使用した補給所は、帰りには使えない。

帰ってくるまでに一度も HP が負にならないようにするための最小コストを求めよ (不可能な場合は -1)。

制約

• 
• 

考えたこと

最初は Greedy に解けないかと考えた。しかし、帰りのことも考えながら、行きで使う補給所を選ぶのは無理そうだった。ならば DP。

帰りの部分については、操作を逆に考えて

---

• 1 進むごとに HP が 1 増えてしまう
• HP が を超えてはいけない
• 補給所では、HP が 未満の場合は だけ減らし、HP が である場合は 以上 以下の任意の値にすることができる

---

というように考えることにした。そうして、次の DP を組む。

dp[i][j][k] ← 番目の補給所にたどり着いた段階で、行き側の HP が 、帰り側の HP が となるようにする場合の最小コスト (座標 0 を 0 番目の補給所とみなす)

計算量は となる。

コード

#include<bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1<<30;
int main() {
    int N, H;
    cin >> N >> H;
    vector<int> X(N), P(N-1), F(N-1);
    for (int i = 0; i < N; ++i) cin >> X[i];
    for (int i = 0; i < N-1; ++i) cin >> P[i] >> F[i];
 
    vector<vector<int>> dp(H+1, vector<int>(H+1, INF));
    for (int j = 0; j <= H; ++j) dp[H][j] = 0;
    
    int prev = 0;
    for (int i = 0; i < N; ++i) {
        vector<vector<int>> ndp(H+1, vector<int>(H+1, INF));
        
        int dif = X[i] - prev;
        
        // 補給しない
        for (int j = 0; j <= H; ++j) {
            for (int k = 0; k <= H; ++k) {
                if (j + dif <= H && k - dif >= 0) {
                    chmin(ndp[j][k], dp[j + dif][k - dif]);
                }
            }
        }
        if (i < N - 1) {
            // 行き
            for (int j = 0; j < H; ++j) {
                for (int k = 0; k <= H; ++k) {
                    if (j - F[i] >= 0 && j - F[i] + dif <= H && k - dif >= 0) {
                        chmin(ndp[j][k], dp[j - F[i] + dif][k - dif] + P[i]);
                    }
                }
            }
            for (int pj = max(0, H - F[i]); pj <= H; ++pj) {
                for (int k = 0; k <= H; ++k) {
                    if (pj + dif <= H && k - dif >= 0) {
                        chmin(ndp[H][k], dp[pj + dif][k - dif] + P[i]);
                    }
                }
            }
            
            // 帰り
            for (int j = 0; j < H; ++j) {
                for (int k = 0; k <= H; ++k) {
                    if (k + F[i] >= H) {
                        if (j + dif <= H && H - dif >= 0) {
                            chmin(ndp[j][k], dp[j + dif][H - dif] + P[i]);
                        }
                    } else {
                        if (j + dif <= H && k + F[i] - dif >= 0) {
                            chmin(ndp[j][k], dp[j + dif][k + F[i] - dif] + P[i]);
                        }
                    }
                }
            }
        }
        swap(dp, ndp);
        prev = X[i];
    }
    
    int res = INF;
    for (int v = 0; v <= H; ++v) chmin(res, dp[v][v]);
    cout << (res < INF ? res : -1) << endl;
}