#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = (1 << 16) + 1;
const ll inf = 1e9 + 7;
string s;
ll c[N],dp[N],n,cnt[20][30],sz[30];
ll LCP(ll mask){
if (c[mask] != -1) return c[mask];
ll tmp[30]; fill(tmp,tmp + 27,inf);
for (ll i = 0;i < n;i++){
if (((mask >> i) & 1) == 0) continue;
for (ll j = 0;j < 26;j++)
tmp[j] = min(tmp[j],cnt[i][j]);
}
ll ans = 0;
for (ll j = 0;j < 26;j++) ans += tmp[j];
return c[mask] = ans;
}
ll f(ll mask){
if (__builtin_popcount(mask) == 1) return LCP(mask);
ll &res = dp[mask];
if (res != -1) return res;
ll nw = mask; res = inf;
while(nw){
nw = ((nw - 1) & mask);
res = min(res,f(nw) + f(mask ^ nw) - LCP(mask));
}
return res;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
cin>>n;
for (ll i = 0;i < n;i++){
cin>>s; sz[i] = s.size();
for (ll j = 0;j < s.size();j++) cnt[i][s[j] - 'a']++;
}
memset(dp,-1,sizeof(dp)); memset(c,-1,sizeof(c));
cout<<f((1 << n) - 1) + 1;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
vjestica.cpp: In function 'int main()':
vjestica.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (ll j = 0;j < s.size();j++) cnt[i][s[j] - 'a']++;
| ~~^~~~~~~~~~
vjestica.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
720 KB |
Output is correct |
| 2 |
Correct |
1 ms |
720 KB |
Output is correct |
| 3 |
Correct |
1 ms |
720 KB |
Output is correct |
| 4 |
Correct |
489 ms |
848 KB |
Output is correct |
| 5 |
Correct |
481 ms |
920 KB |
Output is correct |
| 6 |
Correct |
425 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
445 ms |
1288 KB |
Output is correct |
| 8 |
Correct |
468 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
451 ms |
1320 KB |
Output is correct |
| 10 |
Correct |
445 ms |
1320 KB |
Output is correct |
