yukicoder No.357 品物の並び替え (Middle)

問題

問題概要

数字を並び替えた時に、条件を満たし、もっとも得点を獲得できる時の得点を求める。

解法

数字の数の最大値が14である。数字をすべて並び替える解法だと、計算量が(n!)になるので、TLE。そのためには計算量を(2ⁿ)にしなければならない。そこで、どの数字を使っているかという集合を考える。そして考えている集合に対して、集合に含まれていない数字を集合に含まれる数字の末尾に付け加える。末尾に付け加えた数字により、スコアが増えるので、その時の集合のスコアの最大を更新していく。
実際には
dp[mask] = max(dp[mask], dp[mask ^ (1 << i)] + sum)
のような漸化式を考えてやった。いわゆるもらうdp?? 集合maskの時のスコアの最大値を、集合maskの中からiビット目をなくした集合にibit目の数字を末尾に足したときのスコアの最大値をdpで計算士した。なぜこのような方法でうまくいくかは、集合が小さいほうから大きいほうへループを回しいるので、ibit目をなくした集合におけるスコアの最大値はibit目を含んでいる元の集合を考えるときにはすでに決定しているからである。

ミス

一発AC

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[mask] := mask集合の時のscoreの最大値
int dp[(1 << 15)];

bool contain(int mask, int pos){
    if((mask & (1 << pos)) != 0) return true;
    return false;
}

int main(void){
    int n, m; cin >> n >> m;
    vector<pair<int, int> > v(m);
    vector<int> score(m);
    rep(i, m) cin >> v[i].first >> v[i].second >> score[i];
    rep(i, (1 << 15)) dp[i] = 0;//初期化
    for (int mask = 1; mask < (1 << n); ++mask){
        for (int i = 0; i < n; ++i){
            if(contain(mask, i)){//ibit目が立っている
                int sum = 0;
                for (int j = 0; j < m; ++j){//j番目の品物とスコアの情報
                    //集合ないの数字に集合に含まれない数字を末尾につけてscoreの最大値を求める
                    if(v[j].second == i && contain(mask, v[j].first)){
                        sum += score[j];
                    }
                    dp[mask] = max(dp[mask], dp[mask ^ (1 << i)] + sum);
                }
            }
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}