SRM469 Div1 Medium(500) TheMoviesLevelTwoDivOne

TheMoviesLevelTwoDivOne

深さ優先探索。ある組み合わせの映画を観ることができるならば、どの順番で観ても以降の映画に影響が無いので、最初に現れた（辞書順最小の）ときのみ調べる。

#include <vector>
#include <algorithm>

using namespace std;

class TheMoviesLevelTwoDivOne
{
    int n;
    vector<int> length;
    vector<int> scary;
    vector<bool> visit;     //  添字の組み合わせの映画を調べたか
    vector<int> movie;
    vector<int> answer;

    void BT();

public:
    vector <int> find( vector <int> length, vector <int> scary );   
};

vector <int> TheMoviesLevelTwoDivOne::find( vector <int> length, vector <int> scary )
{
    n = (int)length.size();
    this->length = length;
    this->scary = scary;
    visit.clear();
    visit.resize( 1<<n );
    movie.clear();
    answer.clear();

    BT();

    for ( int i=0; i<n; i++ )
        if ( std::find( answer.begin(), answer.end(), i ) == answer.end() )
            answer.push_back( i );

    return answer;
}

void TheMoviesLevelTwoDivOne::BT()
{
    //  これまでに観た映画の組み合わせをビットで表現
    int b = 0;
    for ( int i=0; i<(int)movie.size(); i++ )
        b |= 1 << movie[i];

    //  すでに調べていれば終了
    if ( visit[b] )
        return;

    if ( movie.size() > answer.size() )
        answer = movie;

    if ( (int)movie.size() == n )
        return;

    int s = 74;
    for ( int i=0; i<(int)movie.size(); i++ )
        s += 47 - length[movie[i]];

    for ( int i=0; i<n; i++ )
    if ( std::find( movie.begin(), movie.end(), i ) == movie.end() )
    {
        if ( s >= scary[i]  &&  s + 47 >= length[i] )
        {
            movie.push_back( i );
            BT();
            movie.pop_back();
        }
    }

    visit[b] = true;
}