제출 #299008

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

vjestica

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

typedef long long ll;

ll cnt[25][26];
ll dp[1000005];
ll cc[26];

const int INF = 1000000009;

string s[20];

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    for(int i=1; i<(1<<n); i++) dp[i] = INF;
    for(int i=1; i<=n; i++){
        cin >> s[i];
        for(auto c : s[i]){
            cnt[i][c-'a']++;
        }
        dp[(1<<(i-1))] = s[i].size();
    }
    for(int mask=1; mask<(1<<n); mask++){
        int mxpref = 0;
        for(int i=0; i<26; i++) cc[i] = INF;
        for(int i=1; i<=n; i++){
            if((1<<(i-1)) & mask){
                for(int j=0; j<26; j++) cc[j] = min(cc[j], cnt[i][j]);
            }
        }
        for(int i=0; i<26; i++) mxpref += cc[i];
        for(int j=mask; j; j=(j-1)&mask){
            if(j == mask) continue;
            dp[mask] = min(dp[mask], -mxpref + dp[j] + dp[j^mask]);
        }
    }
    cout << dp[(1<<n)-1]+1;
    return 0;
}

• Subtask 1: 160 / 160