perogram

No.561 東京と京都

Quiz

https://yukicoder.me/problems/no/561

Submit

https://yukicoder.me/submissions/336212

解法

  • 動的計画法を使う
  • dp[2][N]
    • dp[i][j]
    • i : 0:東京 1:京都
    • j : j日目 (0-index)の仕事を終えた後のお金
  • とする
  • 前日の稼ぎと当日の稼ぎの関係は
    • 前日東京→
      • 当日東京
      • 当日京都(交通費を払う)
    • 前日京都→
      • 当日東京(交通費を払う)
      • 当日京都
  • この分岐で、より稼げる方を選んでdp配列を埋めていけばいい
    • 「稼ぎの多い方」:max関数を使う

感想

  • 旅行・お仕事・お金など身近な感じが良い
  • DPの入門にもいい
  • DPは苦手意識があるのでBlogでも多く取り上げていきたい
  • コードを下に載せてみる。includeなどは除外してエッセンスのみ

Code

int main(){
    // input
    ll N, D;
    cin >> N >> D;

    vector<ll> T(N);
    vector<ll> K(N);
    FOR(i, 0, N){
        cin >> T.at(i);
        cin >> K.at(i);
    }

    ll dp[2][N];
    dp[0][0] = T[0];
    dp[1][0] = K[0] - D;

    FOR(i, 1, N){
        dp[0][i] = max(dp[0][i-1] + T[i], dp[1][i-1] - D + T[i]);
        dp[1][i] = max(dp[1][i-1] + K[i], dp[0][i-1] - D + K[i]);
    }

    ll answer = max(dp[0][N-1], dp[1][N-1]);
    p(answer);
    
    return 0;
}