diff options
Diffstat (limited to '22.16/main.cpp')
| -rw-r--r-- | 22.16/main.cpp | 25 |
1 files changed, 9 insertions, 16 deletions
diff --git a/22.16/main.cpp b/22.16/main.cpp index 8ccabed..9f7641a 100644 --- a/22.16/main.cpp +++ b/22.16/main.cpp @@ -1,3 +1,4 @@ +#include <algorithm> #include <deque> #include <iostream> #include <string> @@ -50,28 +51,21 @@ void findLengths(Graph &g, int base) { Graph g; -void rec(vector<int> path, vector<int> &avail, int time, int score) { - cout << score << "\t" << time << "\t"; - for (int n : path) - cout << n << ","; - cout << endl; - - int cur = path.back(); +int rec(int cur, vector<int> &avail, int time, int score) { + int best = score; for (int i = 0; i < avail.size(); i++) { int n = avail[i]; if (n == 0) continue; avail[i] = 0; - vector<int> path2 = path; - path2.push_back(n); - int time2 = time + g.dist[{cur, n}] + 1; - if (30 < time2) continue; - int score2 = score + g.rates[n] * (30 - time2); - - rec(path2, avail, time2, score2); + if (time2 < 30) { + int score2 = score + g.rates[n] * (30 - time2); + best = max(best, rec(n, avail, time2, score2)); + } avail[i] = n; } + return best; } int main() { @@ -97,6 +91,5 @@ int main() { for (int base : nonzero) findLengths(g, base); - vector<int> start = {0}; - rec(start, nonzero, 0, 0); + cout << rec(0, nonzero, 0, 0) << endl; } |