제출 #1319418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319418		vicvic	Vještica (COCI16_vjestica)	C++20	160 / 160	60 ms	1056 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;
const int NMAX=16;
int n;
string input[NMAX+5];
int dp[(1 << NMAX)+5], cnt[NMAX+5][50], mn[50];
int main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    for (int i=0;i<n;i++)
    {
        cin >> input[i];
        input[i]='#'+input[i];
        for (int j=1;j<input[i].size();j++)
            cnt[i][input[i][j]-'a']++;
        dp[1 << i]=(int)input[i].size()-1;
    }
    for (int i=0;i<1 << n;i++)
    {
        if (__builtin_popcount (i)<=1)
            continue;
        dp[i]=1e9;
        for (int j=i;;)
        {
            j=(j-1)&i;
            if (j==0)
                break;
            dp[i]=min (dp[i], dp[j]+dp[i^j]);
        }
        for (int j=0;j<26;j++)
            mn[j]=1e9;
        for (int j=0;j<n;j++)
        {
            if (i & (1 << j))
            {
                for (int z=0;z<26;z++)
                    mn[z]=min (mn[z], cnt[j][z]);
            }
        }
        for (int j=0;j<26;j++)
            dp[i]-=mn[j];
    }
    cout << dp[(1 << n)-1]+1;
    return 0;
}

• Subtask 1: 160 / 160