結果

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

---

テストケース

ソースコード

#include<stdio.h>
int MAX(int a,int b){return a<b?b:a;}
int main(){
  int n,s=0,a,i,j,k,m[20][20],d[(1<<16)+10]={};
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    s+=a;
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++)scanf("%d",&m[i][j]);
  }
  for(i=0;i<(1<<n);i++){
    for(j=0;j<n;j++){
      if(i&(1<<j))continue;
      for(k=a=0;k<n;k++){
	if(i&(1<<k))a+=m[k][j];//,printf("%d %d\n",i,k);
      }//printf("%d\n",a);
      d[i|(1<<j)]=MAX(d[i|(1<<j)],d[i]+a);
    }
    //for(j=0;j<(1<<n);j++)printf("%d ",d[j]);printf("\n");
  }
  printf("%d\n",s-d[(1<<n)-1]);
  //printf("%d\n",d[(1<<n)-1]);
  return 0;
}