結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const int INF = (int)1e9;

int dp[(1<<16) + 10];
int T[20];
int A[20][20];

int main(){
  int N;
  cin >> N;
  rep(i,N){
    cin >> T[i];
  }
  rep(i,N){
    rep(j,N){
      cin >> A[i][j];
    }
  }

  rep(i,(1<<16)+10) dp[i] = INF;
  dp[0] = 0;
  
  for(int S=0; S<(1<<N); S++){
    rep(i,N){
      if(((S>>i)&1) == 0){
        int t = T[i];
        rep(j,N){
          if((S>>j)&1){
            t -= A[j][i];
          }
        }
        dp[S | (1<<i)] = min(dp[S | (1<<i)], dp[S] + t);
      }
    }
  }

  cout << dp[(1<<N)-1] << endl;
  
  return 0;
}