제출 #146746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146746		vex	Vještica (COCI16_vjestica)	C++14	48 / 160	2069 ms	1916 KiB

vjestica

#include<bits/stdc++.h>
#define maxn 17
#define INF 10000000
using namespace std;

int n;
string s[maxn];
int sl[maxn][26];
int dp[(1<<maxn) + 5];
vector<int>sz[maxn];
vector<int>tre;
int minn[26];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        for(auto x:s[i])
        {
            sl[i][x-'a']++;
        }
    }

    for(int i=1;i<(1<<n);i++)
    {
        int br=0;
        for(int j=1;j<=i;j*=2)
        {
            br+= (j & i)!=0;
        }
        sz[br].push_back(i);
    }


    for(int br=1;br<=n;br++)
    {
        for(auto subset:sz[br])
        {
            tre.clear();
            for(int j=0;j<n;j++)
            {
                if((1<<j)&subset)tre.push_back(j);
            }

            if(br==1)
            {
                dp[subset]=s[tre[0]].size();
                continue;
            }

            for(int j=0;j<26;j++)minn[j]=INF;
            for(int j=0;j<br;j++)
            {
                for(int w=0;w<26;w++)
                {
                    minn[w]=min(minn[w],sl[ tre[j] ][w]);
                }
            }
            int presek=0;
            for(int j=0;j<26;j++)presek+=minn[j];

            /*if(subset==3)
            {
                cout<<presek<<endl;
            }*/

            dp[subset]=INF;
            for(int j=1;j<(1<<br)-1;j++)
            {
                int subsub1=0;
                int subsub2=0;
                for(int w=0;w<br;w++)
                {
                    if(j&(1<<w))subsub1+=1<<(tre[w]);
                    else subsub2+=1<<(tre[w]);
                }

                /*if(subset==3)
                {
                    cout<<subsub1<<" "<<subsub2<<endl;
                }*/
                dp[subset]=min(dp[subset],dp[subsub1]+dp[subsub2]-presek);
            }
        }
    }

    //cout<<endl<<endl;

    /*vector<int>v;
    for(int i=1;i<(1<<n);i++)
    {
        v.clear();
        for(int j=0;(1<<j)<=i;j++)
        {
            if(i&(1<<j))
            {
                v.push_back(j);
            }
        }
        cout<<v.size()<<": ";
        for(auto x:v)cout<<x<<" ";cout<<endl;

        cout<<dp[i]<<endl<<endl;
    }*/
    cout<<dp[(1<<n)-1]+1<<endl;
    return 0;
}

• Subtask 1: 48 / 160