제출 #202305

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

vjestica

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 16 + 5;

int a[20][30], b[30];
int dp[(1 << 16) + 10], lcp[(1 << 16) + 10];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	int len = 0;
	for (int i = 0; i < n; i++){
		string s;
		cin >> s;
		for (int mask = 0; mask < (1 << n); mask++)
			if (mask & (1 << i))
				dp[mask] += (int)s.size();
		len += (int)s.size();
		for (int j = 0; j < (int)s.size(); j++)
			a[i][(int)s[j] - 'a'] ++;
	}
	for (int mask = 1; mask < (1 << n); mask ++){
		for (int j = 0; j < 26; j++)
			b[j] = len;
		for (int j = 0; j < n; j++)
			if (mask & (1 << j))
				for (int x = 0; x < 26; x++)
					b[x] = min(a[j][x], b[x]);
		for (int i = 0; i < 26; i++)
			lcp[mask] += b[i];
	}
	dp[0] = 0;
	for (int mask = 0; mask < (1 << n); mask++){
		for (int sub = mask; sub; sub = (sub - 1) & mask){
			if (mask == sub)
				continue;
			dp[mask] = min(dp[mask], dp[sub] + dp[mask ^ sub] - lcp[mask]);
		}
	}
	cout << dp[(1 << n) - 1] + 1 << '\n';
}

• Subtask 1: 160 / 160