結果

提出番号 2204
提出者 matsukin1111
言語 C++
提出日時 2019-02-21 17:41:25
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 5ms 23296KB
2 AC 100% 5ms 23312KB
3 AC 100% 5ms 23296KB
4 AC 100% 5ms 23296KB
5 AC 100% 5ms 23280KB
6 AC 100% 6ms 23280KB
7 AC 100% 5ms 23296KB
8 AC 100% 4ms 23296KB
9 AC 100% 5ms 23296KB
10 AC 100% 6ms 23296KB
11 AC 100% 9ms 23296KB
12 AC 100% 8ms 23296KB
13 AC 100% 9ms 23296KB
14 AC 100% 9ms 23280KB
15 AC 100% 7ms 23312KB
16 AC 100% 6ms 23296KB
17 AC 100% 5ms 23296KB
18 AC 100% 6ms 23296KB
19 AC 100% 15ms 23280KB
20 AC 100% 13ms 23296KB
21 AC 100% 5ms 23296KB
22 AC 100% 34ms 23280KB
23 AC 100% 6ms 23296KB
24 AC 100% 50ms 23296KB
25 AC 100% 13ms 23296KB
26 AC 100% 25ms 23312KB
27 AC 100% 59ms 23312KB
28 AC 100% 15ms 23296KB
29 AC 100% 341ms 23296KB
30 AC 100% 27ms 23296KB

ソースコード


#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

int INF = 101010;
int n;
int dp[(1<<16)+1][18];
vector<int>t(20);
vector<vector<int>>a(20, vector<int>(20, 0));




int rec(int bit,int v) {
	if (dp[bit][v] != -1)return dp[bit][v];
	if (bit == (1 << v))return dp[bit][v] = t[v];

	int res = INF;

	int prev_bit = bit & ~(1 << v);

	rep(u, 0, n) {
		if (!(prev_bit & (1 << u)))continue;
		int temp = rec(prev_bit,u)+t[v];
		rep(k, 0, n) {
			if (bit&(1 << k))temp -= a[k][v];
		}
		if (res > temp)res = temp;
	}

	return dp[bit][v] = res;
}





int main() {
	cin >> n;
	rep(i, 0, n) {
		cin >> t[i];
	}
	rep(i, 0, n)rep(j, 0, n)cin >> a[i][j];

	int res = INF;
	rep(i, 0, n) {
		memset(dp, -1, sizeof(dp));
		res = min(res, rec((1<<n)-1,i));
	}

	cout << res << endl;


	return 0;
}