結果

提出番号 2220
提出者 ndifix
言語 C++
提出日時 2019-03-18 13:56:49
問題名 (70)アルゴリズムのお勉強
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 2ms 8560KB
2 WA 0% 2ms 7872KB
3 WA 0% 2ms 8336KB
4 WA 0% 2ms 7872KB
5 WA 0% 2ms 7872KB
6 WA 0% 2ms 7888KB
7 WA 0% 2ms 8784KB
8 WA 0% 2ms 8080KB
9 WA 0% 2ms 7888KB
10 WA 0% 2ms 8160KB
11 WA 0% 2ms 8544KB
12 WA 0% 2ms 8112KB
13 WA 0% 2ms 7872KB
14 WA 0% 2ms 7856KB
15 WA 0% 2ms 7856KB
16 WA 0% 2ms 8160KB
17 WA 0% 2ms 8160KB
18 WA 0% 2ms 8112KB
19 WA 0% 3ms 7888KB
20 WA 0% 3ms 8128KB
21 WA 0% 2ms 8320KB
22 WA 0% 4ms 8144KB
23 WA 0% 2ms 8064KB
24 WA 0% 6ms 7872KB
25 WA 0% 3ms 7904KB
26 WA 0% 4ms 7936KB
27 WA 0% 6ms 8144KB
28 WA 0% 3ms 8096KB
29 WA 0% 20ms 8096KB
30 WA 0% 4ms 8768KB

ソースコード

#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
#define mod 1000000007
using namespace std;

int n, t[16], a[16][16];
int dp[131072]; //dp[x]=min for making x

int func(unsigned int I){
	if(dp[I]!=inf) return dp[I];
	for(int i=0;i<n;i++){
		if(I & (1<<i)){
			for(int j=0;j<n;j++)	if((I&~(1<<i))&(1<<j))	dp[I]=min(dp[I], func((I&~(1<<i)))+t[i]-a[j][i]);
		}
	}
	return dp[I];
}

int main(){
	/*
	n=3; t[0]=5;t[1]=6;t[2]=7;
	a[0][0]=0;a[0][1]=1;a[0][2]=2;
	a[1][0]=1;a[1][1]=0;a[1][2]=1;
	a[2][0]=2;a[2][1]=2;a[2][2]=0;
	*/
	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];
	
	for(int i=1;i<131072;i++)dp[i]=inf;
	dp[0]=0;
	for(int i=0;i<n;i++)dp[int(pow(2.0,i))]=t[i];
	unsigned int full=pow(2.0,n)-1;
	
	cout<<func(full)<<endl;

	/*for(int i=0;i<=n;i++){
	for(int j=0;j<=full;j++){
		if(bitset<5>(j).count()==i)cout<<bitset<5>(j)<<" "<<func(j)<<endl;
	}}*/
	return 0;
}