アルゴリズム::白準::DP:14501::退社


質問する



質問リンク
商談がうまくいけば、白俊に最大の収益をもたらす計画を立ててください.

質問へのアクセス

  • は、本開発において、同様の問題をブルートフォードで解決する方法を説明している.
    https://velog.io/@embeddedjun/アルゴリズム-Back-Breutforce-14501-終了
  • を解く方法は同じです.DPを使うだけなので、bruteforceよりも早く答えを見つけることができます.
  • であっても,この問題は注釈配列を用いていないため,Brutforeの時間的複雑さとほぼ同じである.
  • 任意の日付を選択する場合もあれば、選択せずに次の日に移る場合もあります.
  • Base condition 1. 範囲を超える
  • Base condition 2.
  • 、今日のお問い合わせが選択できない場合は

    コード#コード#

    // https://www.acmicpc.net/problem/14501
    #include <iostream>
    using namespace std;
    
    static int N, memo[15];
    static pair<int, int> sched[15];
    
    int solve(int day) {
        if (day >= N) return 0;	// [기저]: 범위 초과
        if (day + sched[day].first > N) return solve(day + 1);	// [기저]: 다음 날로 넘어갈 수 밖에 없는 경우.
        if (memo[day] != 0) return memo[day];   // [기저]: 이미 메모이제이션 된 값.
        // 해당 날짜를 택하는 경우와 택하지 않고 넘어가는 경우를 나눠서 계산한다.
        return memo[day] = max(sched[day].second + solve(day + sched[day].first), solve(day + 1));
    }
    
    int main() {
        ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
        cin >> N;
        for (int i = 0; i < N; ++i) cin >> sched[i].first >> sched[i].second;
        cout << solve(0) << '\n';
    }

    結果