LiveArchive 6904 Travel Card

問題

何日目に対して、バスに乗る回数と電車に乗る回数が与えられる。
バス、電車それぞれに1回乗る券の他に、
1日バス乗り放題券、1日バス・電車乗り放題券
7日バス乗り放題券、7日バス・電車乗り放題券
30日バス乗り放題券、30日バス・電車乗り放題券
が存在する。それぞれ値段が決まっている。
日間のバスと電車の乗る回数の予定が与えられるので、費用を最小化せよ。

解法

バスの券を長く使う間、途中で電車の券を数回買う、という操作にも対応できるように、バスと電車のそれぞれについて残り日数を状態として持っておくと良い。残り日数は最大30日(1日目をすぐ使うと考えると最大29日)の状態を持てれば良い。

template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }

typedef long long ll;
ll const inf = 1e10;

ll dp[10001][31][31];

int main() {

  int Tc; cin >> Tc;
  rep(_, Tc) {
    int N; cin >> N;
    vector<int> bus(N), train(N);
    rep(i, N) cin >> bus[i] >> train[i];

    rep(i, 10001) rep(j, 31) rep(k, 31) dp[i][j][k] = inf;

    dp[0][0][0] = 0;

    rep(i, N) {
      rep(j, 31) {
        rep(k, 31) {
          if(j > 0 && k > 0) {
            minimize(dp[i+1][j-1][k-1], dp[i][j][k]);
          } else if(j > 0) {
            minimize(dp[i+1][j-1][0],   dp[i][j][0] + train[i] * 2);
            minimize(dp[i+1][j-1][0],   dp[i][j][0] + 6);
            minimize(dp[i+1][j-1][6],   dp[i][j][0] + 36);
            minimize(dp[i+1][j-1][29],  dp[i][j][0] + 90);
          } else if(k > 0) {
            minimize(dp[i+1][0][k-1],   dp[i][0][k] + bus[i]);
            minimize(dp[i+1][0][k-1],   dp[i][0][k] + 3);
            minimize(dp[i+1][6][k-1],   dp[i][0][k] + 18);
            minimize(dp[i+1][29][k-1],  dp[i][0][k] + 45);
            minimize(dp[i+1][0][0],     dp[i][j][0] + 6);
            minimize(dp[i+1][6][6],     dp[i][j][0] + 36);
            minimize(dp[i+1][29][29],   dp[i][j][0] + 90);
          } else {
            minimize(dp[i+1][0][0],     dp[i][0][k] + bus[i] + train[i] * 2);
            minimize(dp[i+1][0][0],     dp[i][0][k] + 3 + train[i] * 2);
            minimize(dp[i+1][6][0],     dp[i][0][k] + 18 + train[i] * 2);
            minimize(dp[i+1][29][0],    dp[i][0][k] + 45 + train[i] * 2);
            minimize(dp[i+1][0][0],     dp[i][j][0] + 6);
            minimize(dp[i+1][6][6],     dp[i][j][0] + 36);
            minimize(dp[i+1][29][29],   dp[i][j][0] + 90);
          }
        }
      }
    }

    ll ans = inf;
    rep(i, 30) rep(j, 30) {
      minimize(ans, dp[N][i][j]);
    }

    cout << ans << endl;

  }

  return 0;
}

感想

minimize(...) が多くの行数に渡ってしまったが、バグを埋め込ませずにうまくforを回す方法はあるだろうか。