[ABC320] F - Fuel Round Trip

[Q] https://atcoder.jp/contests/abc320/tasks/abc320_f

考察
1. NとHが300なので、DP[300][300][300]でできないか考える。
2. 「ガソリンスタンドが1度しか使えない」の条件が厳しすぎる。bitset<300>で使ったスタンドを管理する、とかは無理そう。
3. なので、復路のときに、そのガソリンスタンドを使ったかどうか考える必要をなくしたい。ガソリンスタンドを見るときに、1回で往路と復路を同時に見たい。
4. ガソリンスタンドのindexを進めるごとに、
a. 往路では、残っているガソリンの量を管理
b. 復路では、必要なガソリンの量を同時に管理する。
5. DP[300][300][300] // DP[index][往路で残っているガソリンh0][復路で必要なガソリンh1]で管理すればできそう
6. 答えは折り返し地点のindexNについて、
DP[N][往路のh0][復路のh1]のうち、h0>=h1であるDPの最小値を求める。

入力例1
4 10 // N H
2 5 9 11 // X
8 10 // P F
5 8
4 9

初期値
DP[0][10][0]:0 // 地点0において、往路のガソリン10 復路で必要なガソリンは0

X[0] = 2
DP[1][8][0]:8 // 復路でガソリン補充。復路で地点2に到達した時点で、必要なガソリンは0
DP[1][8][2]:0 // 補充しない
DP[1][10][2]:8 // 往路でガソリン補充した。往路のガソリンは10

X[1] = 5
DP[2][5][0]:5
DP[2][5][3]:8
DP[2][5][5]:0 // 補充しない
DP[2][7][0]:13
DP[2][7][5]:8
DP[2][10][3]:13
DP[2][10][5]:5

X[2] = 9
DP[3][1][0]:4
DP[3][1][4]:5
DP[3][1][7]:8
DP[3][1][9]:0 // 補充しない 残りガソリン1で、9->11に進むのに2必要だから、このデータは淘汰される
DP[3][3][0]:12
DP[3][3][4]:13
DP[3][3][9]:8
DP[3][6][0]:9
DP[3][6][7]:13
DP[3][6][9]:5
DP[3][10][4]:9
DP[3][10][7]:12
DP[3][10][9]:4

X[3] = 11 // 折り返し地点 ガソリンの補充を考慮しない
DP[4][1][2]:12
DP[4][1][6]:13
DP[4][4][2]:9
DP[4][4][9]:13
DP[4][8][6]:9
DP[4][8][9]:12

解答の候補になるのは、往路のガソリン>=復路で必要なガソリンである、以下の2つ
DP[4][4][2]:9
DP[4][8][6]:9

最小値の9が答え。

実装

ll DP[301][301][301]; // idx, 往路の残りH0, 復路で必要なh1

int main() {
  cincout();

  ll N, H;
  cin >> N >> H;
  vector<ll> X(N), P(N - 1), F(N - 1);
  rep(i, N) cin >> X[i];
  rep(i, N - 1) { cin >> P[i] >> F[i]; }

  rep(i, N + 1) rep(j, H + 1) rep(k, H + 1) DP[i][j][k] = oo;
  // 初期値
  rep(i, H + 1) DP[0][H][0] = 0; // 往路はガソリンH, 復路の0地点での必要なガソリンは0
  rep(i, N) {
    ll dis = X[i];
    if (i > 0) dis -= X[i - 1];
    for (ll h0 = H; h0 >= 0; --h0) {
      for (ll h1 = 0; h1 <= H; ++h1) {
        if (DP[i][h0][h1] == oo) continue;
        if (h0 - dis >= 0 && h1 + dis <= H) { // 往路で進んでガソリンが残っている && 復路で進んでガソリンが足りる
          chmin(DP[i + 1][h0 - dis][h1 + dis], DP[i][h0][h1]); // なんも補給しない
          if (i < N - 1) {
            // 往路で補給する
            chmin(DP[i + 1][min(H, h0 - dis + F[i])][h1 + dis], DP[i][h0][h1] + P[i]);
            // 復路で補給する
            chmin(DP[i + 1][h0 - dis][max(0LL, h1 - F[i] + dis) ], DP[i][h0][h1] + P[i]);
          }
        }
      }
    }
  }
  ll ans = oo;
  rep(i, H + 1) for (ll j = 0; j <= i; ++j) { // i:往路で残ったガソリン <= j:復路で必要なガソリン
    if (DP[N][i][j] == oo) continue;
    chmin(ans, DP[N][i][j]);
  }
  auto debug = [&]() {
    rep(i, N + 1) rep(j, H + 1) rep(k, H + 1) {
      if (DP[i][j][k] == oo) continue;
      cerr << "DP[" << i << "][" << j << "][" << k << "]:" << DP[i][j][k]
           << endl;
    }
  };
  //debug();
  if (ans == oo) ans = -1;
  cout << ans << endl;
}

https://atcoder.jp/contests/abc320/submissions/45650244