結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

const int INF = 1 << 29;
int T[20];
int A[20][20];
int dp[1<<16];

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

    int N; cin >> N;
    REP(i, N) cin >> T[i];
    REP(i, N) REP(j, N) cin >> A[i][j];

    REP(i, 1<<N) dp[i] = INF;
    dp[0] = 0;

    REP(mask, 1<<N) {
        REP(i, N) {
            if (mask & (1 << i)) continue;
            int tmp = 0;
            REP(j, N) if (mask & (1 << j)) tmp += A[j][i];
            dp[mask|(1<<i)] = min(dp[mask|(1<<i)], dp[mask] + T[i] - tmp);
        }
    }

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