Advertisement
Josif_tepe

Untitled

Apr 20th, 2022
693
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. int n, m, k;
  6. struct vraboten {
  7.     int plata, br_predmeti;
  8.     vector<int> predmet;
  9. };
  10. int dp[202][1 << 8][1 << 8];
  11. vraboten vraboteni[100], kandidati[220];
  12. int rec(int at, int p1, int p2) {
  13.     if(__builtin_popcount(p1) == n and __builtin_popcount(p2) == n) {
  14.         return 0;
  15.     }
  16.     if(at == k) {
  17.         return 1e9;
  18.     }
  19.     if(dp[at][p1][p2] != -1) {
  20.         return dp[at][p1][p2];
  21.     }
  22.     int result = 1e9;
  23.     int t1 = p1, t2 = p2;
  24.     for(int i = 0; i < kandidati[at].br_predmeti; i++) {
  25.         int x = kandidati[at].predmet[i];
  26.         if(t1 & (1 << x)) {
  27.             t2 |= (1 << x);
  28.         }
  29.         else {
  30.             t1 |= (1 << x);
  31.         }
  32.     }
  33.     result = min(result, rec(at + 1, t1, t2) + kandidati[at].plata);
  34.     result = min(result, rec(at + 1, p1, p2));
  35.     return dp[at][p1][p2] = result;
  36. }
  37. int main() {
  38.     cin >> n >> m;
  39.     int p1 = 0, p2 = 0;
  40.     int suma_plata = 0;
  41.     for(int i = 0; i < m; i++) {
  42.         cin >> vraboteni[i].plata >> vraboteni[i].br_predmeti;
  43.         suma_plata += vraboteni[i].plata;
  44.         for(int j = 0; j < vraboteni[i].br_predmeti; j++) {
  45.             int x;
  46.             cin >> x;
  47.             x--;
  48.             vraboteni[i].predmet.push_back(x);
  49.             if(p1 & (1 << x)) {
  50.                 p2 |= (1 << x);
  51.             }
  52.             else {
  53.                 p1 |= (1 << x);
  54.             }
  55.         }
  56.     }
  57.     cin >> k;
  58.     for(int i = 0; i < k; i++) {
  59.         cin >> kandidati[i].plata >> kandidati[i].br_predmeti;
  60.         for(int j = 0; j < kandidati[i].br_predmeti; j++) {
  61.             int x;
  62.             cin >> x;
  63.             x--;
  64.             kandidati[i].predmet.push_back(x);
  65.         }
  66.     }
  67.     memset(dp, -1, sizeof dp);
  68.     cout << rec(0, p1, p2) + suma_plata << endl;
  69.     return 0;
  70. }
  71.  
Advertisement
RAW Paste Data Copied
Advertisement