結果

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

---

テストケース

ソースコード

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

#define int long long

int N;
vector<int> dp;
vector<int> t;
vector<vector<int> > a;

int dfs(int bit) {
  if ( dp[bit] >= 0 ) return dp[bit];
  if ( bit == (1<<N)-1 ) return 0;  

  int ret = (int)1e9;  
  for ( int i = 0; i < N; i++ ) {
    if ( (1<<i) & bit ) continue;
    int add = t[i];    
    for ( int j = 0; j < N; j++ ) {
      if ( (1<<j) & bit ) add = max(0LL, add-a[j][i]);      
    }
    ret = min(ret, dfs(bit|(1<<i))+add);	      
  }  

  return dp[bit] = ret;  
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  
  cin >> N;
  
  t = vector<int>(N);
  for ( int i = 0; i < N; i++ ) cin >> t[i];

  a = vector<vector<int> >(N, vector<int>(N));
  for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j < N; j++ ) cin >> a[i][j];    
  }

  dp = vector<int>(1<<N, -1);
  cout << dfs(0) << endl;
  
  return 0;
}