結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll  n,t[20],a[20][20];
	cin>>n;
	for(int i=0;i<n;i++)cin>>t[i];
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
	ll dp[1<<n];
	ll yan=0;
	for(int i=0;i<n;i++)yan+=t[i];
	
	for(int i=0;i<(1<<n);i++)dp[i]=yan;
	dp[0]=0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			ll cnt=0;
			for(int k=0;k<n;k++){
				if(i&(1<<k))cnt+=a[k][j];
			}
			dp[i|1<<j]=min(dp[i|1<<j],dp[i]+t[j]-cnt);
		}
	}
	cout<<dp[(1<<n)-1]<<endl;
	return 0;
}