結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
typedef long long ll;
using std::cout;
using std::endl;
using std::cin;

int main(){
	int n; cin >> n; std::vector<int> a(n);
	std::vector<std::vector<int>> li(n, std::vector<int>(n));
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> li[i][j];
	
	std::vector<int> dp(1 << n, 0);
	for(int i = 1; i < (1 << n); i++) dp[i] = 1e9;
	
	for(int i = 0; i < (1 << n); i++) {
		for(int j = 0; j < n; j++) {
			if((i >> j) & 1) continue;
			
			int tmp = a[j];
			for(int k = 0; k < n; k++) {
				if((i >> k) & 1) tmp -= li[k][j];
			}
			
			dp[i | (1 << j)] = std::min(dp[i | (1 << j)], dp[i] + tmp);
		}
	}
	
	cout << dp[(1 << n) - 1] << endl;
	return 0;
}