DP bitmask - COCI - LQDOJ - Vjestica

//Make CSP great again
//You're as beautiful as the day I lost you
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 16;
int cnt[N][26];
int dp[1 << N], n;
void read()
{
    cin >> n;
    for (int i = 0; i < n; ++ i)
    {
        string s;
        cin >> s;
        for (char c : s)
        {
            ++cnt[i][c - 'a'];
        }
    }
}
int prefix(int mask)
{
    int h[26];
    fill(h, h + 26, 1e9);
    for (int i = 0; i < n; ++ i)
    {
        if (mask & (1 << i))
        {
            for (int j = 0; j < 26; ++ j)
            {
                h[j] = min(h[j], cnt[i][j]);
            }
        }
    }
    int ret = 0;
    for (int i = 0; i < 26; ++ i)
    {
        ret += h[i];
    }
    return ret;
}
int f(int mask)
{
    if (mask == 0)
    {
        return 0;
    }
    int &res = dp[mask];
    if (res != -1)
    {
        return res;
    }
    int pre = prefix(mask);
    if (__builtin_popcount(mask) == 1)
    {
        return res = pre;
    }
    res = 1e9;
    for (int i = (mask - 1) & mask; i > 0; i = (i - 1) & mask)
    {
        res = min(res, f(i) + f(mask ^ i) - pre);
    }
    return res;
}
void solve()
{
    memset(dp, -1, sizeof(dp));
    cout << f((1 << n) - 1) + 1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}