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;
}