#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,int> pint;
typedef string str;
int dp[(1<<16)];
int n;
int niz[16][26];
int ima[17];
int main()
{
// valjda ce proci iz 100 pokusaja i posle 200 optimizacija
ios;
cin>>n;
for(int i=0;i<n;i++){
str a;
cin>>a;
for(char j:a) niz[i][j-'a']++;
}
//if(n>13) return -1;
for(int mask=1;mask<(1<<n);mask++){
int ret=0;
if(__builtin_popcount(mask)==1){
int sta=-1;
for(int i=0;i<n;i++) if(mask&(1<<i)) sta=i;
for(int i=0;i<26;i++){
ret+=niz[sta][i];
}
dp[mask]=ret;
continue;
//cout<<bitset<5>(mask)<<" "<<ret<<"\n";
}
int bitovi=__builtin_popcount(mask);
int tren=0;
for(int j=0;j<n;j++){
if(mask&(1<<j)){
//cout<<j<<"\n";
ima[tren]=j;
tren++;
}
}
for(int i=0;i<26;i++){
int koliko=1e6+1;
for(int j=0;j<bitovi;j++){
koliko=min(koliko,niz[ima[j]][i]);
}
ret+=koliko;
}
//cout<<" "<<bitset<5>(mask)<<" "<<ret<<" "<<"\n";
//cout<<bitovi<<" "; for(int i:ima) cout<<i<<" "; cout<<"\n";
int sta=1e6+1;
if(bitovi==2){
sta=min(sta,dp[(1<<ima[bitovi-2])]+dp[(1<<ima[bitovi-1])]-ret);
}
for(int i=0;i<(1<<(bitovi-2));i++){
int nova1=(1<<ima[bitovi-1]);
//cout<<nova1<<"\n";
int nova2=0;
for(int j=0;j<bitovi-2;j++){
if(i&(1<<j)){
nova1+=(1<<ima[j]);
}else{
nova2+=(1<<ima[j]);
}
}
if(i==(1<<bitovi-2)-1){
sta=min(sta,dp[nova1]+dp[nova2+(1<<ima[bitovi-2])]-ret);
}else{
sta=min(sta,dp[nova1+(1<<ima[bitovi-2])]+dp[nova2]-ret);
sta=min(sta,dp[nova1]+dp[nova2+(1<<ima[bitovi-2])]-ret);
}
//cout<<" "<<bitset<5>(mask)<<" "<<bitset<5>(nova1)<<" "<<bitset<5>(nova2)<<"\n";
}
//cout<<bitset<5>(mask)<<" "<<sta<<"\n";
dp[mask]=sta;
}
cout<<dp[(1<<n)-1]+1;
return 0;
}
Compilation message
vjestica.cpp: In function 'int main()':
vjestica.cpp:87:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
87 | if(i==(1<<bitovi-2)-1){
| ~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
292 ms |
628 KB |
Output is correct |
| 5 |
Correct |
311 ms |
748 KB |
Output is correct |
| 6 |
Correct |
302 ms |
876 KB |
Output is correct |
| 7 |
Correct |
304 ms |
1256 KB |
Output is correct |
| 8 |
Correct |
304 ms |
1516 KB |
Output is correct |
| 9 |
Correct |
299 ms |
1124 KB |
Output is correct |
| 10 |
Correct |
338 ms |
1228 KB |
Output is correct |
