結果

提出番号	2189
提出者	siser
言語	C++
提出日時	2018-11-27 20:14:46
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repr(i,a,b) for(int i=(a); i>=(b); i--)
#define all(x) (x).begin(),(x),end()
typedef long long ll;
const int INF=1<<29;

int N;
int t[20];
int a[20][20];
//dp[S]:部分集合Sだけの問題を解くときにかかる最短の時間
int dp[(1<<16)+10];

int main(){
    
    cin>>N;
    rep(i,0,N)cin>>t[i];
    rep(i,0,N)rep(j,0,N)cin>>a[i][j];
    
    //bitDP
    //初期化
    rep(i,0,1<<N)dp[i]=INF;
    //dp初期条件:dp[0]=0;
    dp[0]=0;
    //dp漸化式:Sの部分集合を全列挙
    //dp[msk+{i}]=min(dp[msk+{i}],dp[msk+{i}]+t[i]-a[j][i])(j∈msk)
    rep(msk,0,1<<N) rep(i,0,N){
        if(!(msk & (1<<i))){//iが部分集合mskに含まれないときは追加処理を行える
            int k=0;
            rep(j,0,N){
                //jがmskに含まれるとき、その数だけ時間は減る(2重に縮まる可能性を考慮する)
                if(msk & (1<<j))k-=a[j][i];
            }
            dp[msk+(1<<i)]=min(dp[msk+(1<<i)],dp[msk]+t[i]+k);
        }
    }
    //求める値:dp[(1<<N)-1](全てのフラグが立っている)
    cout<<dp[(1<<N)-1]<<endl;
    
    return 0;
}