Benelux Algorithm Programming Contest 2016 D Bridge Automation

問題

橋の下をN隻の船がくぐります。船がくぐるには、橋を上げないといけません。
橋を上げる、もしくは下すのには60秒かかります。
船が橋をくぐるのには20秒かかります。
また、船は橋の前に到着してから1800秒(30分)待機することができます。
船が到着する時刻が昇順で与えられるので、橋を上げている時間を最小にしたうえで出力してください、というものです。

解法

DPを考えます。

• dp[i] = i番目までの船がくぐり終えるまでの、橋があがっている時間の最小値

とすると、

• dp[i] = min(dp[j-1]+jからiを一度の橋の上げ下ろしですべて通したときにかかる時間)
  となります。
  j番目からi番目の船をいっぺんに通すことを考えると、
  橋をあげておろすのに120秒、そしてj番目の船が通過を開始してからi番目の船が通過を終えるまでが
  20+ max(i番目の到着時刻 - j番目の到着時刻 - 1800 , 20 × (i - j) )
  となります。
  max()の右側が、j番目からi番目までの船がきれいに連続して通過できた場合、左側がきれいに通過できずにどこかで待機時間が生じてしまった場合になります。
  ということで、あとはこの計算を繰り返していけば答えが求まります。

提出コードは以下になります。

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

int n;
int memo[4005] = {0};
int dp[4005] = {0};

int solve();

int main() {
  int i;
  cin >> n;
  for(i = 0; i < n; ++i) cin >> memo[i];
  for(i = 0; i < n; ++i) dp[i] = 100000000;
  cout << solve() << endl;
  return 0;
}

int solve() {
  int i, j, now = 0;
  // j~i go one time. dp[i] = min(dp[j-1] + j~i time).
  for(i = 0; i < n; ++i)
    for(j = 0; j <= i; ++j) {
      now =
          140 + max(memo[i] - memo[j] - 1800, 20 * (i - j));
      if(j == 0)
        dp[i] = now;
      else
        dp[i] = min(dp[i], now + dp[j - 1]);
    }
  return dp[n - 1];
}