結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
#define chmin(a, b) a = min(a, b)
using namespace std;
typedef pair<int, int> P;
const int INF = 1e15;

int dp[1 << 16];

signed main(){
    int n;
    cin >> n;
    vector<int> t(n);
    rep(i, 0, n) cin >> t[i];
    vector<vector<int> > a(n, vector<int>(n));
    rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
    rep(i, 0, 1 << 16) dp[i] = INF;
    dp[0] = 0;
    for(int mask = 0; mask < (1 << n); mask++){
        rep(i, 0, n){
            if(mask & (1 << i)) continue;
            int tmp = t[i];
            rep(j, 0, n){
                if(mask & (1 << j)) tmp -= a[j][i];
            }
            chmin(dp[mask | (1 << i)], dp[mask] + tmp);
        }
    }
    cout << dp[(1 << n) - 1] << endl;
}