Advertisement
Josif_tepe

Untitled

Mar 16th, 2021
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <map>
  7. #include <stack>
  8. using namespace std;
  9. typedef long long ll;
  10. const int INF = 1e9;
  11. const int maxn = 21;
  12. int n, x;
  13. int a[maxn];
  14. pair<int, int> dp[1 << maxn];
  15.  
  16. int main()
  17. {
  18.     ios_base::sync_with_stdio(false);
  19. //    ifstream cin("in.txt");
  20.     cin >> n >> x;
  21.     for(int i = 0; i < n; i++) {
  22.         cin >> a[i];
  23.     }
  24.     dp[0] = make_pair(1, 0);
  25.     for(int mask = 1; mask < (1 << n); mask++) {
  26.         dp[mask] = make_pair(n + 1, 0);
  27.         for(int i = 0; i < n; i++) {
  28.             if(mask & (1 << i)) {
  29.             pair<int, int> tmp = dp[mask ^ (1 << i)];
  30.             if(tmp.second + a[i] <= x) {
  31.                 tmp.second += a[i];
  32.             }
  33.             else {
  34.                 tmp.first += 1;
  35.                 tmp.second = a[i];
  36.             }
  37.             dp[mask] = min(dp[mask], tmp);
  38.             }
  39.            
  40.         }
  41.     }
  42.     cout << dp[(1<<n) - 1].first << endl;
  43.    
  44.         return 0;
  45. }
  46. /*
  47.  
  48.  4 10
  49.  4 8 6 1
  50.  
  51.  4 + 6
  52.  8 + 1
  53.  
  54.  f(taken) --> f(taken2)
  55.  
  56.  f(0000) --> f(1000) + 0
  57.  f(1000) --> f(1010) + 1
  58.  
  59.  dp[taken][2]
  60.  dp[taken][0] --> minimum weight sum of people till the previous move
  61.  dp[taken][1] --> minimum number of elevator rides
  62.  
  63.  8 6 4 1
  64.  
  65.  dp[taken] --> minimum number of elevator calls till this mask
  66.  
  67.  // 2 ^ 20 -->
  68.    27 40 16 50
  69.  
  70.  f(taken, left) --> f(taken2, left + a[j])
  71.  
  72.  f(1111)
  73.  
  74.  pair<int, int> dp[1 << n];
  75.  dp[0] = make_pair(0, x)
  76.  
  77.  
  78.  */
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement