#include <stdio.h>
#include <string.h>
#define N 16
#define A 26
#define L 1000000
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int main() {
static char cc[L + 1];
static int kk[N][A], ll[1 << N], dp[1 << N];
int n, i, a, b, c;
scanf("%d", &n);
for (i = 0; i < n; i++) {
int l, h;
scanf("%s", cc), l = strlen(cc);
for (h = 0; h < l; h++)
kk[i][cc[h] - 'a']++;
}
for (b = 1; b < 1 << n; b++)
for (a = 0; a < A; a++) {
int k = INF;
for (i = 0; i < n; i++)
if ((b & 1 << i) != 0)
k = min(k, kk[i][a]);
ll[b] += k;
}
for (b = 1; b < 1 << n; b++)
if ((b & b - 1) == 0)
dp[b] = ll[b];
else {
dp[b] = INF, c = 0;
while ((c = c - b & b) != b)
dp[b] = min(dp[b], dp[c] + dp[b ^ c] - ll[b]);
}
printf("%d\n", dp[(1 << n) - 1] + 1);
return 0;
}
Compilation message
vjestica.c: In function 'main':
vjestica.c:34:14: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
34 | if ((b & b - 1) == 0)
| ~~^~~
vjestica.c:38:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
38 | while ((c = c - b & b) != b)
| ~~^~~
vjestica.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
vjestica.c:20:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%s", cc), l = strlen(cc);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
284 KB |
Output is correct |
| 4 |
Correct |
131 ms |
896 KB |
Output is correct |
| 5 |
Correct |
127 ms |
804 KB |
Output is correct |
| 6 |
Correct |
127 ms |
1036 KB |
Output is correct |
| 7 |
Correct |
134 ms |
1160 KB |
Output is correct |
| 8 |
Correct |
157 ms |
1204 KB |
Output is correct |
| 9 |
Correct |
129 ms |
1220 KB |
Output is correct |
| 10 |
Correct |
129 ms |
1208 KB |
Output is correct |
