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 }