結果

提出番号	1633
提出者	nxteru
言語	C++
提出日時	2018-08-04 13:18:32
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
int n,t[20],a[20][20],dp[1<<17];
int main(void){
    cin>>n;
    for(int i=0;i<n;i++)cin>>t[i];
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
    for(int i=0;i<1<<n;i++)dp[i]=20000;
    dp[0]=0;
    for(int k=0;k<1<<n;k++){
        for(int i=0;i<n;i++){
            if(!(k>>i&1)){
                int s=t[i];
                for(int j=0;j<n;j++)if(k>>j&1)s-=a[j][i];
                dp[k|(1<<i)]=min(dp[k|(1<<i)],dp[k]+s);
            }
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
}