oj.uz

답안 #114808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114808 2019-06-03T03:33:06 Z zoooma13 Vještica (COCI16_vjestica) C++14
160 / 160
 376 ms 1016 KB 
#include <bits/stdc++.h>
using namespace std;

int lg2[1<<16];

int n;
string s;
vector <int> ch_cnt[16];

int dp[1<<16];
int solve(int bts){
    if((bts&(bts-1)) == 0){
        int idx = lg2[bts&-bts] ,ret = 0;
        for(int c=0; c<26; c++)
            ret += ch_cnt[idx][c];
        return ret;
    }
    if(~dp[bts])
        return dp[bts];

    vector <int> mi(26 ,INT_MAX);
    for(int b=bts; b; b-=(b&-b)){
        int idx = lg2[b&-b];
        for(int c=0; c<26; c++)
            mi[c] = min(mi[c] ,ch_cnt[idx][c]);
    }
    int all_mi = 0;
    for(int c=0; c<26; c++)
        all_mi += mi[c];

    int ans = INT_MAX;
    for(int b=bts; b; b=(b-1)&bts){
        if(b && (bts^b))
            ans = min(ans ,solve(b)+solve(bts^b));
    }

    return dp[bts] = ans-all_mi;
}

int main()
{
    lg2[0] = -1;
    for(int i=1; i<(1<<16); i++){
        lg2[i] = lg2[i-1];
        if((i&(i-1)) == 0)
            lg2[i]++;
    }

    cin >> n;
    for(int i=0; i<n; i++){
        ch_cnt[i].resize(26);
        cin >> s;
        for(char c='a'; c<='z'; c++)
            ch_cnt[i][c-'a'] = count(s.begin() ,s.end() ,c);
    }

    memset(dp ,-1 ,sizeof dp);
    cout << solve((1<<n)-1)+1 << endl;
}

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 362 ms 896 KB Output is correct
5 Correct 365 ms 896 KB Output is correct
6 Correct 369 ms 936 KB Output is correct
7 Correct 370 ms 888 KB Output is correct
8 Correct 376 ms 888 KB Output is correct
9 Correct 371 ms 1016 KB Output is correct
10 Correct 371 ms 888 KB Output is correct