제출 #107608

#제출 시각아이디문제언어결과실행 시간메모리
107608MilkiVještica (COCI16_vjestica)C++14
48 / 160
2039 ms1152 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = a; i < b; ++i) #define REP(i, n) FOR(i, 0, n) #define _ << " " << #define sz(x) ((int) x.size()) #define pb(x) push_back(x) #define TRACE(x) cerr << #x << " = " << x << endl typedef long long ll; typedef pair<int, int> point; const int MAXN = 17, MAX = 1 << 17, ABC = 27, inf = 1e9; int n; int dp[MAX], let[MAXN][ABC]; int get(int mask){ int tmp[26]; REP(i, 26) tmp[i] = inf; REP(i, n){ if( (mask & (1 << i)) == 0) continue; REP(j, 26) tmp[j] = min(tmp[j], let[i][j]); } int ret = 0; REP(i, 26) ret += tmp[i]; return ret; } int rek(int mask){ if(dp[mask]) return dp[mask]; if(__builtin_popcount(mask) == 1) return dp[mask] = get(mask); int sub = get(mask); vector <int> tmp; REP(i, n){ if((1 << i) & mask) tmp.pb(i); } int ret = inf; FOR(i, 1, (1 << sz(tmp))){ int newMask = 0; REP(j, sz(tmp)) if(i & (1 << j)) newMask |= (1 << tmp[j]); if(newMask == 0 || (newMask ^ mask) == 0) continue; ret = min(ret, rek(newMask) + rek(newMask ^ mask) - sub); } return dp[mask] = ret; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; REP(i, n){ string s; cin >> s; REP(j, sz(s)) let[i][s[j] - 'a'] ++; } cout << rek((1 << n) - 1) + 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...