oj.uz

답안 #168683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168683 2019-12-15T09:27:20 Z dolphingarlic Vještica (COCI16_vjestica) C++14
0 / 160
 2000 ms 888 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;
unordered_map<char, int> cnt[16];
int dp[1 << 16];

int solve(int mask) {
    int ans = INT_MAX, common = 0, old_mask = mask;

    if (~dp[mask]) return dp[mask];
    if (!mask) return dp[mask] = 0;

    // cout << mask << endl;

    unordered_map<char, int> diff;
    for (char i = 'a'; i <= 'z'; i++) {
        diff[i] = INT_MAX;
        FOR(j, 0, n) if (mask & (1 << j)) diff[i] = min(diff[i], cnt[j][i]);
        common += diff[i];
    }
    FOR(i, 0, n) {
        if (mask & (1 << i)) {
            if (diff == cnt[i]) mask -= (1<<i);
            else for (char j = 'a'; j <= 'z'; j++) cnt[i][j] -= diff[j];
        }
    }

    if (!mask) return dp[old_mask] = common;

    FOR(i, (common == 0), mask) {
        if ((mask & i) == i) ans = min(ans, solve(i) + solve(mask - i));
    }

    FOR(i, 0, n) {
        if (mask & (1 << i)) {
            for (char j = 'a'; j <= 'z'; j++) cnt[i][j] += diff[j];
        }
    }
    return dp[old_mask] = ans + common;
}

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]++;
    }
    cout << solve((1 << n) - 1) + 1;
    return 0;
}

Subtask #1
0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 632 KB Output isn't correct
2 Incorrect 31 ms 632 KB Output isn't correct
3 Incorrect 23 ms 632 KB Output isn't correct
4 Execution timed out 2070 ms 632 KB Time limit exceeded
5 Incorrect 1729 ms 680 KB Output isn't correct
6 Incorrect 1684 ms 728 KB Output isn't correct
7 Incorrect 1313 ms 884 KB Output isn't correct
8 Incorrect 1648 ms 760 KB Output isn't correct
9 Incorrect 1749 ms 880 KB Output isn't correct
10 Incorrect 1664 ms 888 KB Output isn't correct