oj.uz

답안 #168910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168910 2019-12-17T05:39:55 Z dolphingarlic Vještica (COCI16_vjestica) C++14
160 / 160
 760 ms 804 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 if it has more than 1 bit
- If it has only 1 bit, the size of the trie is simply the number of letters in that word
- solve(mask) = min(solve(A) + solve(B)) where A + B = mask, A & mask == A, B & mask == B, and A & B == 0
- To do this efficiently, we iterate over all submasks of mask
- Complexity: O(3^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;
}

void solve(int mask) {
    int pref = get_pref(mask);
    if (__builtin_popcount(mask) == 1) {
        dp[mask] = pref;
        return;
    }

    dp[mask] = INT_MAX;
    for (int i = mask & (mask - 1); i; i = mask & (i - 1)) {
        dp[mask] = min(dp[mask], dp[i] + dp[mask ^ i] - pref);
    }
}

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)) solve(i);

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

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 636 KB Output is correct
2 Correct 10 ms 632 KB Output is correct
3 Correct 10 ms 632 KB Output is correct
4 Correct 701 ms 664 KB Output is correct
5 Correct 701 ms 760 KB Output is correct
6 Correct 743 ms 724 KB Output is correct
7 Correct 742 ms 804 KB Output is correct
8 Correct 760 ms 632 KB Output is correct
9 Correct 752 ms 760 KB Output is correct
10 Correct 751 ms 760 KB Output is correct