aboutsummaryrefslogtreecommitdiff
path: root/dp_solver.cpp
diff options
context:
space:
mode:
authorTa180m2019-05-07 16:23:09 -0500
committerGitHub2019-05-07 16:23:09 -0500
commitca8ee0759ada3db70d74076c942dab881823c54b (patch)
treebdfec46738903ee2d9fb919f9541211301270d41 /dp_solver.cpp
parent5402bd0b0408373f8647e0dfefccb6c501011c59 (diff)
Update dp_solver.cpp
Fixed a bug involving the mega bonus
Diffstat (limited to 'dp_solver.cpp')
-rw-r--r--dp_solver.cpp16
1 files changed, 8 insertions, 8 deletions
diff --git a/dp_solver.cpp b/dp_solver.cpp
index eb35371..055990c 100644
--- a/dp_solver.cpp
+++ b/dp_solver.cpp
@@ -13,17 +13,14 @@ typedef long long ll;
// Initial conditions
// Change these values to alter the initial state
-ll start = 0, goal = 1e10;
+ll start = 0, goal = 1e10; // Start and end amounts
int max_it = 150; // Number of iterations to solve
int MPQ = 0, SB = 0, M = 0; // Initial upgrade status
int D = 0, R = 0, B1 = 0, B2 = 0; // Initial power-up status
-// Initial state
-int s = 3600 * MPQ + 360 * SB + 36 * M + 18 * D + 9 * R + 3 * B1 + B2;
-
// State: Iteration, Upgrade status, Power-up status
-// DP stores maximum possible money for each state
-// pre used to reconstruct optimal strategy
+// DP array stores maximum possible money for each state
+// pre array used to reconstruct optimal strategy
ll DP[7200000], pre[7200000];
// Upgrade values
@@ -64,6 +61,9 @@ int main() {
// Initialize DP array
memset(DP, -1, sizeof(DP));
+ // Calculate initial state
+ int s = 3600 * MPQ + 360 * SB + 36 * M + 18 * D + 9 * R + 3 * B1 + B2;
+
// Set initial value
DP[s] = start;
for (int i = 0; i < 36000 * max_it; i++) {
@@ -138,8 +138,8 @@ int main() {
// Buy the mini bonus
if (B1 == 0 && DP[i] - pcost(2, DP[i]) > DP[i + 2]) {
- DP[i + 2] = DP[i] - pcost(2, DP[i]);
- pre[i + 2] = i;
+ DP[i + 3] = DP[i] - pcost(2, DP[i]);
+ pre[i + 3] = i;
}
// Buy the mega bonus