fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(v) (v).begin(), (v).end()
  4. #define int long long
  5. #define sz(v) (int)(v).size()
  6. #define mod 998244353
  7.  
  8. const int MB= 21;
  9. const int MN= 101;
  10. map<string, int> mp;
  11. int cnt;
  12.  
  13. void solve() {
  14.         string str, T;
  15.         vector<pair<int, int>> vs;
  16.         int B= 0;
  17.  
  18.         while (getline(cin, str)) {
  19.  
  20.                 B++;
  21.                 istringstream ss(str);
  22.                 int j= 0, nm= 0, mask= 0;
  23.  
  24.                 do {
  25.                         if (!j) {
  26.                                 ss >> T;
  27.                                 nm= stoi(T);
  28.                         } else {
  29.                                 ss >> T;
  30.                                 if (mp.count(T)) {
  31.                                         mask|= (1<< mp[T]);
  32.                                 } else {
  33.                                         mp[T]= cnt;
  34.                                         mask|= (1<< cnt);
  35.                                         cnt+= 1;
  36.                                 }
  37.                         }
  38.                         j++;
  39.  
  40.                 }while (ss);
  41.  
  42.                 vs.push_back({nm, mask});
  43.         }
  44.  
  45.         vector<int> dp((1<< cnt));
  46.  
  47.         for (int kk= 0; kk< 1<<(cnt); kk++) dp[kk]= (-1);
  48.  
  49.  
  50.         int val= (1<< cnt)- 1;
  51.  
  52.         function<int(int)> calc= [&](int msk)->int{
  53.                 if (msk== val) {
  54.                         return 0;
  55.                 }
  56.  
  57.                 int &ret= dp[msk];
  58.                 if (ret!= -1)return ret;
  59.                 ret= 1e18;
  60.  
  61.                 for (int i= 0; i< B; i++) {
  62.                         ret= min(ret, calc(msk| vs[i].second)+ vs[i].first);
  63.                 }
  64.  
  65.                 return ret;
  66.         };
  67.  
  68.         cout << calc(0)<< "\n";
  69. }
  70.  
  71. int32_t main(){
  72.         int T= 1;
  73.         //cin >> T;
  74.         while ( T-- ) {
  75.                 solve();
  76.         }
  77. return 0;
  78. }
  79.  
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
300 Backtracking Dynamic_Programming Greedy
125 Dynamic_Programming
35 Backtracking
85 Greedy
120 Backtracking Dynamic_Programming
80 Greedy Backtracking
stdout
copy 
200
https://ideone.com/6JIKiX
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!