#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 17);
int n;
int a[100][30], s[20];
int dp[N], f[N];
int calc(int mask)
{
if(dp[mask] != -1) return dp[mask];
if(mask == 0) return 0;
if(__builtin_popcount(mask) == 1)
{
int i = 0;
for(i; i < n; i++)
if((mask >> i) & 1)break;
return s[i];
}
for(int j = 0;j < 26; j ++)
{
int x = 1e9 + 7;
for(int i = 0; i < n; i ++)
if((mask >> i) & 1)
x=min(a[i][j], x);
f[mask] += x;
}
int ans=1e9 + 7;
for(int i = (mask-1) & mask; i > 0; i = (i - 1)&mask)
ans=min(ans, calc(i) + calc(mask ^ i) - f[mask]);
return dp[mask] = ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
memset(dp, -1, sizeof dp);
cin >> n;
for(int i = 0; i < n; i++)
{
string t;
cin >> t;
s[i] = t.size();
for(int j = 0;j < t.size(); j++)
a[i][t[j] - 'a'] ++;
}
cout << calc((1 << n) - 1) + 1;
return 0;
}
Compilation message
vjestica.cpp: In function 'int calc(int)':
vjestica.cpp:17:7: warning: statement has no effect [-Wunused-value]
17 | for(i; i < n; i++)
| ^
vjestica.cpp: In function 'int main()':
vjestica.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int j = 0;j < t.size(); j++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
292 ms |
1228 KB |
Output is correct |
| 5 |
Correct |
292 ms |
1320 KB |
Output is correct |
| 6 |
Correct |
294 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
296 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
290 ms |
1760 KB |
Output is correct |
| 9 |
Correct |
295 ms |
1620 KB |
Output is correct |
| 10 |
Correct |
292 ms |
1724 KB |
Output is correct |
