SRM468 Div1 500 TheMovieLevelTwoDivOne

問題

• n(≦20)個のホラー映画を見る順番を決める
• Johnの初期HPは74。1分につき1ずつ減少し，-0.5になると眠りに落ちる。
• 映画iの時間scary[i]になるとHPが47回復する
• 眠りに着く前に見れる映画の数を最大化する順番を答える。同点なら辞書順最小を。

解法

• メモ付き深さ優先探索
• 見た映画をビット集合で管理する

#include <iostream>
#include <vector>

using namespace std;

class TheMoviesLevelTwoDivOne{
private:
    int n, num;
    bool mem[1<<20];
    int  used;
    vector<int> ans, length, scary;
    void dfs(vector<int> &cur, int pos, int cnt, int lest){
        for(int i=0;i<n;i++){
            if((used>>i)&1) continue;
            if(lest >= scary[i] && lest + 47 >= length[i]) {
                used ^= 1<<i;
                if(!mem[used]){
                    mem[used] = true;
                    cur[pos] = i;
                    dfs(cur, pos+1, cnt+1, lest+47-length[i]);
                }
                used ^= 1<<i;
            }
        }
        if(cnt > num){
            num = cnt;
            int idx = pos;
            for(int i=0;i<n;i++)
                if(!((used>>i)&1)) cur[idx++] = i;
            ans = cur;
        }
    }
public:
    vector<int> find(vector<int> _length, vector<int> _scary){
        length = _length;
        scary  = _scary;
        n = length.size();
        num = -1;
        used = 0;
        memset(mem,  false, sizeof(mem) );
        vector<int> cur(n);
        dfs(cur, 0, 0, 74);
        return ans;
    }
};