제출 #98348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98348		dalgerok	Vještica (COCI16_vjestica)	C++17	160 / 160	136 ms	1272 KiB

vjestica

#include<bits/stdc++.h>
using namespace std;


const int N = 16, M = 26;



int n, cnt[N][M], dp[(1 << N)];
string s;


inline int get(int mask){
    int cur[M];
    memset(cur, 63, sizeof(cur));
    for(int i = 0; i < n; i++){
        if((mask >> i) & 1){
            for(int j = 0; j < M; j++){
                cur[j] = min(cur[j], cnt[i][j]);
            }
        }
    }
    int sum = 0;
    for(int i = 0; i < M; i++){
        sum += cur[i];
    }
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    memset(dp, 63, sizeof(dp));
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < (int)s.size(); j++){
            cnt[i][s[j] - 'a'] += 1;
        }
    }
    for(int i = 1; i < (1 << n); i++){
        int pref = get(i);
        if(__builtin_popcount(i) == 1){
            dp[i] = pref;
        }
        else{
            for(int j = (i - 1) & i; j > 0; j = (j - 1) & i){
                dp[i] = min(dp[i], dp[j] + dp[i ^ j] - pref);
            }
        }
    }
    cout << dp[(1 << n) - 1] + 1;
}

• Subtask 1: 160 / 160