結果

提出番号	2191
提出者	toof
言語	C++
提出日時	2018-12-06 21:29:45
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

int main() {
  cin.tie(0); ios::sync_with_stdio(false);

  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];

  int dp[1<<16];
  rep(i, 1<<n) dp[i] = 1000*16+100;
  dp[0] = 0;

  rep(mask, 1<<n) {
    rep(i, n) {
      if (mask & 1<<i) continue;

      int tmp = t[i];
      rep(j, n) {
        if (mask & 1 << j) tmp -= a[j][i];
      }

      dp[mask+(1<<i)] = min(dp[mask+(1<<i)], dp[mask]+tmp);
    }
  }

  cout << dp[(1<<n)-1] << endl;
}