SRM588 Div2 Medium "GUMIAndSongsDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12707

訳

GUMIは歌う事が好きである。彼女はN個の歌をインプットされている。それらには0～N-1の番号がつけられている。彼女は暇な時間ができたため、その時間内にできるだけ多くの歌を歌おうとした。

あなたにintの配列 durationが与えられる。duration[i]はi番目の曲の時間の長さを示す。

GUMIは全く異なるトーンの曲を、連続して歌うのは難しいと気付いた。あなたはintの配列 toneが与えられる。tone[i]はi番目の曲のトーンを示す。そして、x番目の曲を歌い終わってから、y番目の曲を歌うためには、tone[x] - tone[y]の絶対値分だけ、喉の調節の為、時間を使わなくてはならない。

あなたはint Tが与えられる。これはGUMIの暇な時間である。一曲目は喉を調節することなく、即座に歌う事が可能である。彼女が歌う事のできる曲の数の最大値を返せ。

制約

1 <= インプットされた曲の数 <= 15
1 <= duration[i] <= 10^6
1 <= tone[i] <= 10^6
1 <= T <= 10^7

考えた事

toneを低い順に（または高い順に）歌うとよいよね。で、曲の数は高々15なんだから、それぞれの曲を歌うのか？歌わないのか？全探索すればよい。

ソースコード

class GUMIAndSongsDiv2 {
public:

    int N, Time;
    vector<int> D;
    vector<int> T;
    int best;

    void dfs( int id, int n, int d, int t ){
        // 歌いきった・・・
        if( id == N ){
            best = max( best, n );
            return;
        }

        // この曲を歌わない
        dfs( id + 1, n, d, t );

        int nt; 
        // 初歌い
        if( t == 0 ){
            nt = D[id];
        }else{
            nt = d + (T[id] - t) + D[id];
        }

        if( nt <= Time ){
            // この曲を歌う
            dfs( id + 1, n + 1, nt, T[id] );
        }
    }

    int maxSongs(vector <int> duration, vector <int> tone, int _Time){

        N = duration.size();
        D = duration;
        T = tone;
        Time = _Time;

        // tone順に並び替え
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < N - 1; j++ ){
                if( T[j] > T[j+1] ){
                    swap( T[j], T[j+1] );
                    swap( D[j], D[j+1] );
                }
            }
        }

        // dfs
        best = 0;
        dfs( 0, 0, 0, 0 );
        return best;
    }
};