結果

提出番号	1949
提出者	ikd
言語	C++
提出日時	2018-08-04 14:42:34
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)

int main(){

  int n; cin>> n;
  vector<int> t(n);
  rep(i, n) cin>> t[i];
  vector<vector<int>> a(n, vector<int>(n));
  rep(i, n)rep(j, n) cin>> a[i][j];

  vector<int> memo(1<<n, 1e9);
  function<int(int)> f=[&](int bit){
    if(bit==0) return 0;
    if(memo[bit]<1e9) return memo[bit];
    int &ret=memo[bit];
    rep(i, n)if(bit&(1<<i)){
      int tm=t[i];
      rep(j, n)if(bit&(1<<j)) tm-=a[j][i];
      ret=min(ret, f(bit^(1<<i))+tm);
    }
    return ret;
  };

  cout<< f((1<<n)-1)<< endl;
  return 0;
}