用DP做的,大佬帮忙看看哪里不对呗~
#include<iostream>
#include<string.h>
using namespace std;
int dp[14][300005];
// dp[magic][time]
void answer(bool if_ok, int h) {
if (if_ok) cout << "Yes";
else cout << "No";
cout << endl;
cout << h;
cout << endl;
exit(0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, s, t;
cin >> m >> s >> t;
int d = 0; //距离
int tm = 0; //时间
while (m >= 10) {
m -= 10;
d += 60;
tm++;
if (d > s) answer(true, tm);
if (t == tm) answer(false, d);
}
memset(dp, 0, sizeof(dp));
dp[m][tm] = d;
for (int i = tm + 1; i <= t; i++)
for (int x = 0; x < 14; x++) {
if (dp[x][i - 1] > s)
answer(true, i - 1);
//cout << "magic:" << x << "|time:" << i << " ";
dp[x][i] = max(dp[x][i - 1] + 17, dp[x][i - 1]);
//cout << "dp[" << x << "][" << i << "]:" << dp[x][i];
if (x < 10)
dp[x][i] = max(dp[x + 4][i - 1], dp[x][i]);
if (x >= 10)
dp[x][i] = max(dp[x - 10][i - 1] + 60, dp[x][i]);
}
int maxx = 0;
for (int j = 0; j < 14; j++) {
//cout << j <<' '<< t << ' ' << dp[j][t]<< endl;
if (dp[j][t] > maxx) {
maxx = dp[j][t];
if (maxx > s) {
answer(true, t);
return 0;
}
}
}
answer(false, maxx);
return 0;
}