結果

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

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define fordebug int hoge;cin>>hoge;
int n;
int t[16];
int a[16][16];
int dp[1000000];

void go(int stat,int time){
  if(dp[stat]!=0&&dp[stat]<=time) return;
  dp[stat]=time;
  for(int i=0;i<n;i++){
    if(stat&(1<<i)) continue;
    int mt=t[i];
    lp(j,n){
      if(stat&(1<<j)) mt-=a[i][j];
    }
    int hoge=stat;
    hoge|=(1<<i);
    go(hoge,time+mt);
  }
}

int main(){
  cin>>n;
  lp(i,n) cin>>t[i];
  lp(i,n)lp(j,n) cin>>a[i][j];
  go(0,0);
  cout<<dp[(int)pow(2,n)-1]<<endl;
  return 0;
}