[伯俊][三星基出]14501退社する

質問する

コンサルタントの白俊さんが会社を辞めます.
今日からN+1日で辞めるために、残りのN日にできるだけ多くの相談をします.
白俊は秘書にできるだけ多くの相談を依頼し、秘書は1日に1回異なる人に相談を手配した.
各コンサルティングは,コンサルティングを完了するのに要する時間内にTIとコンサルティングを行う際に得られる金額Piからなる.
N=7の場合は、以下のコンサルティングスケジュールを参照してください.

1日のカウンセリングは全部で3日かかりますが、カウンセリング時にもらえる金額は10です.5日間のお問い合わせは2日間かかりますが、受け付けられる金額は15です.
相談にかかる時間は1日以上かかる場合がありますので、すべての相談はできません.例えば、1日に問い合わせを行った場合、2日、3日に問い合わせをすることはできません.2日に問い合わせをすれば、3、4、5、6日には問い合わせができない.
なお、N+1日は会社にいないため、6,7日は相談できません.
退職前にカウンセリングを行う最大の利益は1日、4日、5日にカウンセリングを行うことであり、その際の利益は10+20+15=45である.
商談がうまくいけば、白俊に最大の収益をもたらす計画を立ててください.

入力

第1行はN(1≦N≦15)を与える.
2行目からN行目まで、TIとPiはスペースで区切られ、1日からN日まで順次与えられる.(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

しゅつりょく

1行目は白俊が得られる最大の利益を出力する.

入力例

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

サンプル出力

45

に答える

/* Date: 2020-09-25 */
#include <iostream>

using namespace std;

typedef struct day{
    int T;
    int P;
} day;

day Day[16];   
int N;
int Rst = 0;

void init();
void dfs(int curr, int cnt);

int main(){
    init();
    for(int i = 1; i <= N; i++){
        dfs(i, Day[i].P);
    }
    cout << Rst << endl;
} 

void init(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> Day[i].T >> Day[i].P;
    }
}

void dfs(int curr, int cnt){
    if(curr + Day[curr].T - 1 > N) return;
    if(cnt > Rst) Rst = cnt;
    for(int i = curr + Day[curr].T; i <= N; i++){
        dfs(i, cnt + Day[i].P);
    }
}

問題を読み始めたばかりの頃、チキン配達の問題を思い出した.
M個の中から条件に合うN個を選べるようなのでDFSで解決しました.
試験例に合格するのに30分ぐらいかかりました.
しかし、提出後91%失敗した.
私はここでうろうろしていましたが、最終的にはRstの初期値が-1だったためです.

1
2 5

上記のテストケースを入力すると、利益は0元になります.
比較演算を簡単に行うために便利な−1を初期値として例外があるとは思わなかった.
後で問題を解くときは、初期値を慎重に設定してください.
また、欲しい値が全く得られない場合は、default値がどれくらいあるべきかを考える習慣を身につけましょう.