제출 #133400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133400		Vlatko	Vještica (COCI16_vjestica)	C++14	160 / 160	311 ms	1264 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;


const int maxn = 16;
const int A = 26;
const int inf = 1e9;

int n;
int cnt[maxn][A];
int dp[1<<maxn];

int num_common(int mask) {
	int mincnt[A];
	for (int j = 0; j < A; ++j) {
		mincnt[j] = inf;
	}
	for (int i = 0; i < n; ++i) {
		if (mask & (1 << i)) {
			for (int j = 0; j < A; ++j) {
				mincnt[j] = min(mincnt[j], cnt[i][j]);
			}
		}
	}
	int res = 0;
	for (int j = 0; j < A; ++j) {
		res += mincnt[j];
	}
	return res;
}

int dfs(int mask) {
	int& res = dp[mask];
	if (res != -1) {
		return res;
	}
	int common = num_common(mask);
	// cout << "common(" << bitset<maxn>(mask) << ") = " << common << endl;
	if ((mask == 0 || mask-(mask&-mask)) == 0) {
		// 0 or 1 bit on
		return res = common; // just the length of the word
	}
	res = inf;
	for (int submask = (mask-1) & mask; submask > 0; submask = (submask-1) & mask) {
		res = min(res, -common + dfs(submask) + dfs(mask ^ submask));
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < A; ++j) {
			cnt[i][j] = 0;
		}
		for (char ch : s) {
			++cnt[i][ch-'a'];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << 1 + dfs((1 << n) - 1) << '\n';
	// for (int m = 0; m < (1 << n); ++m) {
	// 	cout << "dp[" << bitset<maxn>(m) << "] = " << dp[m] << endl;
	// }
}

• Subtask 1: 160 / 160