oj.uz

답안 #168908

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168908 2019-12-17T05:31:45 Z dolphingarlic Vještica (COCI16_vjestica) C++14
48 / 160
 2000 ms 1148 KB 
/*
COCI 2016 Vjestica
- Firstly, notice that N is very small. This implies that we should use a bitmask
- For each mask, we split the active words into 2 groups and solve recursively for those
- solve(mask) = min(solve(A) + solve(B)) where A + B = mask, A & mask == A, B & mask == B, and A & B == 0
- Complexity: O(N^2 * 2^N)
*/

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n;
map<char, int> cnt[16];
int dp[1 << 16];

int get_pref(int mask) {
    map<char, int> pref;
    int ans = 0;
    for (char j = 'a'; j <= 'z'; j++) {
        pref[j] = INT_MAX;
        FOR(i, 0, n) {
            if (mask & (1 << i)) pref[j] = min(pref[j], cnt[i][j]);
        }
        ans += pref[j];
    }
    return ans;
}

int solve(int mask) {
    int pref = get_pref(mask);
    if (__builtin_popcount(mask) == 1) return pref;

    int ans = INT_MAX;
    FOR(i, 1, mask) {
        if ((i & mask) == i) {
            ans = min(ans, dp[i] + dp[mask - i] - pref);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n;
    FOR(i, 0, n) {
        for (char j = 'a'; j <= 'z'; j++) cnt[i][j] = 0;
        string s;
        cin >> s;
        for (char j : s) cnt[i][j]++;
    }

    FOR(i, 1, (1 << n)) dp[i] = solve(i);

    cout << dp[(1 << n) - 1] + 1;
    return 0;
}

Subtask #1
48.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 11 ms 632 KB Output is correct
3 Correct 11 ms 636 KB Output is correct
4 Execution timed out 2041 ms 632 KB Time limit exceeded
5 Execution timed out 2051 ms 760 KB Time limit exceeded
6 Execution timed out 2057 ms 888 KB Time limit exceeded
7 Execution timed out 2055 ms 1016 KB Time limit exceeded
8 Execution timed out 2051 ms 1144 KB Time limit exceeded
9 Execution timed out 2047 ms 1136 KB Time limit exceeded
10 Execution timed out 2045 ms 1148 KB Time limit exceeded