Submission #146746

#TimeUsernameProblemLanguageResultExecution timeMemory
146746vexVještica (COCI16_vjestica)C++14
48 / 160
2069 ms1916 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...