Hatena::Grouptopcoder

cou929のTopCoder日記

2010-04-21

Member SRM 468 div1 (過去問)

21:32

Medium - RoadOrFlightHard

昨日の復習. flightをどう扱うかについては, 直前の都市へ陸路できたのか空路へきたのかだけ保存しておけば大丈夫です. これで結構シンプルになります. コードはjackperselさんの記事がとても読みやすかったのでかなり参考にさせてもらいました.

個人的メモ

  • [i%2] で配列をスワップするテクニック
  • 直線的な構造
  • 漸化式
class RoadOrFlightHard {
public:
  long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K) {
    const long long INF = 1000000000000000000LL;
    long long ret = INF;
    vector <int> roadTimes, flightTimes;
    int i, j, k;
    long long dp[2][42][2];

    for (i=0; i<2; i++)
      for (j=0; j<42; j++)
        for (k=0; k<2; k++)
          dp[i][j][k] = INF;

    roadTimes.push_back(roadFirst % roadMod);
    flightTimes.push_back(flightFirst % flightMod);
    
    for (i=1; i<N; i++) {
      roadTimes.push_back(((long long)roadTimes[i-1] * roadProd + roadAdd) % roadMod);
      flightTimes.push_back(((long long)flightTimes[i-1] * flightProd + flightAdd) % flightMod);
    }

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

    for (i=1; i<=N; i++) {
      for (j=0; j<=K; j++)
        dp[i%2][j][0] = dp[i%2][j][1] = INF;
      for (j=0; j<=K; j++) {
        // walk -> walk
        dp[i%2][j][0] = min(dp[i%2][j][0], dp[(i-1)%2][j][0] + roadTimes[i-1]);
        // flight -> walk
        dp[i%2][j][0] = min(dp[i%2][j][0], dp[(i-1)%2][j][1] + roadTimes[i-1]);
        // walk -> flight
        if (j < K)
          dp[i%2][j+1][1] = min(dp[i%2][j+1][1], dp[(i-1)%2][j][0] + flightTimes[i-1]);
        // flight -> flight
        dp[i%2][j][1] = min(dp[i%2][j][1], dp[(i-1)%2][j][1] + flightTimes[i-1]);
      }
    }

    for (i=0; i<=K; i++)
      ret = min(ret, min(dp[N%2][i][0], dp[N%2][i][1]));

    return ret;
  }
};