oj.uz

답안 #133400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
133400 2019-07-20T14:22:48 Z Vlatko Vještica (COCI16_vjestica) C++14
160 / 160
 311 ms 1264 KB 
#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.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 306 ms 656 KB Output is correct
5 Correct 311 ms 760 KB Output is correct
6 Correct 307 ms 1016 KB Output is correct
7 Correct 308 ms 1140 KB Output is correct
8 Correct 308 ms 1188 KB Output is correct
9 Correct 308 ms 1264 KB Output is correct
10 Correct 310 ms 1148 KB Output is correct