結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

int dp[1<<16];
int n,t[55],a[55][55];

int main(){
  cin>>n;
  r(i,n)cin>>t[i];
  r(i,n)r(j,n)cin>>a[i][j];
  r(i,1<<16)dp[i]=1e9;
  dp[0]=0;
  for(int i=0;i<(1<<n);i++){
      if(dp[i]==1e9)continue;
      for(int k=0;k<n;k++){
        if(i&(1<<k))continue;
        int s=t[k];
        r(l,n)if(i&(1<<l))s-=a[l][k];
        dp[i|(1<<k)]=min(dp[i|(1<<k)],dp[i]+s);
      }
  }
  cout<<dp[(1<<n)-1]<<endl;
}