Untitled
unknown
plain_text
a year ago
1.2 kB
7
Indexable
#include <iostream> using namespace std; #define INT_MAX 999999999 int m, d; // m: max energy; d: distance; int runType[5][3]; // runType[i][0] : minutes; runType[i][1] : seconds; runType[i][2] : energy; int dp[45][605]; int solve(int dist, int energy) { if (dist == 0) { if (energy >= 0) { return 0; } else return INT_MAX; } if (energy < 0) return INT_MAX; if (dp[dist][energy] != -1) return dp[dist][energy]; int ans = INT_MAX; for (int i = 0; i < 5; i++) { int tmp = solve(dist-1,energy-runType[i][2]) + (runType[i][0]*60+runType[i][1]); ans = tmp < ans ? tmp : ans; } dp[dist][energy] = ans; return ans; } int main() { freopen("input.txt","r",stdin); int T; cin >> T; for (int tc = 1; tc <= T; tc++) { cin >> m >> d; for (int i = 0; i < 5; i++) { cin >> runType[i][0] >> runType[i][1] >> runType[i][2]; } // Can use memset(dp,-1,sizeof(dp)); instead but sever not allow for (int i = 0; i < 45; i++) { for (int j = 0; j < 605; j++) { dp[i][j] = -1; } } int res = solve(d,m); cout << "Case #" << tc << endl; if (res == INT_MAX) cout << -1 << endl; else cout << res / 60 << " " << res % 60 << endl; } return 0; }
Editor is loading...
Leave a Comment