結果

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

---

テストケース

ソースコード

#include<bits/stdc++.h>
using namespace std;

int N;
int t[16];
int G[16][16];

int mem[(1<<16)];

int solve(int bit){
  if(bit == (1<<N)-1)return 0;
  if( mem[bit]!=-1 )return mem[bit];
  int res=1e9;
  for(int i=0;i<N;i++){
    if(bit>>i&1)continue;
    int cost=t[i];

    for(int j=0;j<N;j++)
      if(bit>>j&1)
        cost-=G[j][i];

    if(cost<0)cost=0;

    res=min(res, cost + solve( bit | (1<<i) ) );
  }
  return mem[bit]=res;
}

int main(){
  memset( mem, -1 , sizeof(mem));
  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>>G[i][j];

  cout<< solve(0) <<endl;
  return 0;
}