algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (2186B)


      1 #include <iostream>
      2 #include <cmath>
      3 #include <vector>
      4 #include <bitset>
      5 
      6 // n = 4
      7 // m = 3
      8 // k = 2
      9 // 
     10 // satisfactions := 1 2 3 4
     11 // 
     12 // [2 1 5]
     13 // [3 4 2]
     14 // 
     15 // 1 after 2 and 4 after 3 get bonuses
     16 // 
     17 // order 2 (2) 
     18 // order 1 (6)
     19 // order 4 (4)
     20 // 
     21 // = 12 (better)
     22 // 
     23 // order 3 (3)
     24 // order 4 (6)
     25 // order 2 (2)
     26 // 
     27 // = 11
     28 // 
     29 // ---
     30 // 
     31 // best selections:
     32 // 
     33 // - max score after the current state given our prior state
     34 // - dp with state of (selected, prior) 
     35 
     36 using namespace std;
     37 
     38 long long solve(vector<long long>& dishes, vector<vector<long long>>& addedSatisfaction, int prior, bitset<20>& consumed, int step, int toEat, vector<vector<long long>>& lookup) {
     39 
     40     unsigned long long mask = consumed.to_ulong();
     41     if(lookup[mask][prior + 1] != -1) {
     42         return lookup[mask][prior + 1];
     43     }
     44 
     45     if(step == toEat) {
     46         lookup[mask][prior + 1] = 0;
     47         return 0;
     48     }
     49 
     50     long long best = 0;
     51 
     52     for(int i = 0; i < consumed.size() && i < dishes.size(); ++i) {
     53         if(consumed[i] == 0) {
     54             consumed[i] = 1;
     55             long long currentSat = dishes[i];
     56             if(prior != -1) {
     57                 currentSat += addedSatisfaction[prior][i];
     58             }
     59 
     60             long long candidate = solve(dishes, addedSatisfaction, i, consumed, step + 1, toEat, lookup) + currentSat;
     61             consumed[i] = 0;
     62 
     63             if(candidate > best) {
     64                 best = candidate;
     65             }
     66         }
     67     }
     68 
     69     lookup[mask][prior + 1] = best;
     70     return best;
     71 }
     72 
     73 int main() {
     74 
     75     int n, m, k;
     76     long long current;
     77 
     78     cin >> n;
     79     cin >> m;
     80     cin >> k;
     81 
     82     vector<long long> dishes {};
     83 
     84     for(int i = 0; i < n; ++i) {
     85         cin >> current;
     86         dishes.push_back(current);
     87     }
     88 
     89     vector<vector<long long>> addedSatisfaction(n, vector<long long>(n, 0));
     90 
     91     for(int i = 0; i < k; ++i) {
     92         int x, y;
     93         long long z;
     94         cin >> y;
     95         cin >> x;
     96         cin >> z;
     97         addedSatisfaction[y - 1][x - 1] = z;
     98     }
     99 
    100     bitset<20> consumed {};
    101     vector<vector<long long>> lookup(1 << n, vector<long long>(n + 1, -1));
    102     cout << solve(dishes, addedSatisfaction, -1, consumed, 0, m, lookup) << endl;
    103 }