제출 #84683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84683		luciocf	Kronican (COCI16_kronican)	C++14	0 / 100	46 ms	12280 KiB

kronican

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 11;
 
const int inf = 1e9+10;
 
typedef pair<int, int> pii;
 
int num[maxn][maxn], n, k;
 
int dp[1<<10][maxn][maxn];
 
int solve(int mask, int pos, int qtd)
{
	int on = 0;
	for (int i = 0; i < n; i++)
		if (mask&(1<<i)) on++;
 
	if (on == k)
	if (qtd == n) return inf;
	if (dp[mask][pos][qtd] != -1) return dp[mask][pos][qtd];
 
	int caso1 = inf;
	for (int i = 0; i < n; i++)
		if (i != pos && (mask&(1<<i)))
			caso1 = min(caso1, solve(mask, i, qtd+1));
 
	if (!(mask&(1<<pos))) return dp[mask][pos][qtd] = caso1;
 
	int caso2 = inf;
	for (int i = 0; i < n; i++)
		if (i != pos && (mask&(1<<i)))
			caso2 = min(caso2, num[pos][i]+solve(mask^(1<<pos), i, qtd+1));
 
	return dp[mask][pos][qtd] = min(caso1, caso2);
}
 
int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> num[i][j];
 
	memset(dp, -1, sizeof dp);
 
	cout << solve((1<<n)-1, 0, 0) << "\n";
}

• Subtask 1: 0 / 100