Advertisement
Fargoth_Cor

DP in sets

Oct 30th, 2018
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. using namespace std;
  5. int main() {
  6.     ofstream out;
  7.     out.open("meetings.out");
  8.     ifstream in;
  9.     in.open("meetings.out");
  10.  
  11.     int n, k;
  12.     in >> n >> k;
  13.     vector<int> a(n + 1);
  14.     vector<int> b(n + 1);
  15.     vector<int> c(n + 1);
  16.     vector<int> dp(1 << n + 1, 0);
  17.     vector<int> ones(1 << n + 1, 0);
  18.     vector<int> last_meeting(1 << n + 1, 0);
  19.     for (int i = 0; i < n; i++) {
  20.         in >> a[i] >> b[i] >> c[i];
  21.     }
  22.     dp[0] = k;
  23.  
  24.     int R = 0;
  25.     for (int mask = 1; mask < (1 << n); mask++) {
  26.         dp[mask] = 200;
  27.         for (int x = 0; x < n; x++) {
  28.             if ((mask & (1 << x)) == 0)
  29.                 continue;
  30.             int prev_mask = mask & ~(1 << x);
  31.             if (dp[prev_mask] == 200)
  32.                 continue;
  33.             if ((dp[prev_mask] >= a[x]) && (dp[prev_mask] <= b[x])) {
  34.                 dp[mask] = dp[prev_mask] + c[x];
  35.                 ones[mask] = ones[prev_mask] + 1;
  36.                 if (ones[mask] > ones[R])
  37.                     R = mask;
  38.                 last_meeting[mask] = x;
  39.                
  40.                 break;
  41.             }
  42.         }
  43.     }
  44.     vector<int> ans;
  45.     out << ones[R] << endl;
  46.     while (R != 0) {
  47.         ans.push_back(last_meeting[R]);
  48.         R = R & ~(1 << last_meeting[R]);
  49.     }
  50.     for (int i = ans.size() - 1; i >= 0; i--) {
  51.         out << ans[i] + 1 << ' ';
  52.     }
  53.     in.close();
  54.     out.close();
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement