#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=7e4+10, A=30, N=20, MAXV=1e6+10;
int n, dp[MAX], mini[A], roz[N];
int ile[N][A];
string s;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>s;
roz[i]=s.size();
for(int j=0; j<s.size(); j++)
ile[i][s[j]-'a']++;
}
for(int i=1; i<(1<<n); i++){
int x=i, l=1;
bool pierw=true;
vector<int>zap;
while(x){
if(x%2){
if(pierw){
for(int j=0; j<='z'-'a'; j++)
mini[j]=ile[l][j];
pierw=false;
}
for(int j=0; j<='z'-'a'; j++)
mini[j]=min(mini[j], ile[l][j]);
zap.pb(l);
}
x/=2, l++;
}
dp[i]=MAXV;
if(__builtin_popcount(i)==1){
dp[i]=roz[zap[0]];
continue;
}
int maxi=0;
for(int j=0; j<='z'-'a'; j++)
maxi+=mini[j];
for(int j=1; j<(1<<int(zap.size()))-1; j++){
int l1=0, x1=j;
int maska=0;
while(x1){
if(x1%2) maska+=(1<<(zap[l1]-1));
x1/=2, l1++;
}
dp[i]=min(dp[i], dp[maska]+dp[i^maska]-maxi);
//cout<<i<<" "<<maska<<" "<<(i^maska)<<" "<<dp[maska]<<" "<<dp[i^maska]<<" "<<maxi<<"\n";
}
}
cout<<dp[(1<<n)-1]+1<<"\n";
}
Compilation message
vjestica.cpp: In function 'int main()':
vjestica.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int j=0; j<s.size(); j++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1287 ms |
688 KB |
Output is correct |
| 5 |
Correct |
1286 ms |
800 KB |
Output is correct |
| 6 |
Correct |
1284 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
1279 ms |
1056 KB |
Output is correct |
| 8 |
Correct |
1291 ms |
1252 KB |
Output is correct |
| 9 |
Correct |
1296 ms |
1148 KB |
Output is correct |
| 10 |
Correct |
1294 ms |
1180 KB |
Output is correct |
