#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define se second
#define fi first
#define pii pair<int, int>
#define sz(x) (int)(x).size()
const int ABC = 26;
const int INF = 1e9 + 3;
inline void solve(){
int n;
cin >> n;
vvi cnt(n, vi(ABC + 1));
vi dp2(1 << n, INF);
for(int i = 0; i < n; i++){
string s;
cin >> s;
for(int j = 0; j < sz(s); j++){
cnt[i][s[j] - 'a']++;
}
dp2[1 << i] = cnt[i].back() = sz(s);
}
vi dp(1 << n);
for(int mask = 1; mask < (1 << n); mask++){
// same common prefix
vi mx(ABC, -1);
for(int bit = 0; bit < n; bit++){
if((mask >> bit) & 1){
for(int j = 0; j < ABC; j++){
if(mx[j] == -1 || cnt[bit][j] < mx[j]){
mx[j] = cnt[bit][j];
}
}
}
}
for(int j = 0; j < ABC; j++){
if(mx[j] != -1){
dp[mask] += mx[j]; // length of maximum common prefix
}
}
}
for(int mask = 1; mask < (1 << n); mask++){
for(int ss = mask & (mask - 1); ss; ss = (ss - 1) & mask){
dp2[mask] = min(dp2[mask], dp2[ss] + dp2[mask ^ ss] - dp[mask]); // splitlemeden önceki prefiximi splitlediğim her iki subtreemde de sayıyorum
}
}
cout << dp2[(1 << n) - 1] + 1 << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
