NOIP 2007 普及组 守望者的逃离

b站视频

https://www.bilibili.com/video/BV1JT4y1S7AU/

• 循环 + 判断

#include using namespace std;int m, s, t;int dis, sec;int main() {cin >> m >> s >> t;dis = s;sec = t;while (true) {if (m >= 10) {m -= 10; s -= 60; t -= 1;//闪优于跑}else if (m >= 6 && s > 34 && t >= 2) {m -= 6; s -= 60; t -= 2;//闪优于跑}else if (m >= 2 && s > 51 && t >= 3) {m -= 2; s -= 60; t -= 3;//闪优于跑}else if (s > 119 && t >= 7) {s -= 120; t -= 7;//闪优于跑}else {s -= 17; t -= 1;//否则，跑}if (s <= 0) {printf("Yes\n%d", sec - t);return 0;}if (t == 0) {printf("No\n%d", dis - s);return 0;}}return 0;}

#include using namespace std;int m, s, t;int a, b;int main() {cin >> m >> s >> t;    for (int i = 1; i <= t; i ++) {    //a选择魔法，如果魔法值不足就休息    if (m >= 10) m -= 10, a += 60;else m += 4;//b选择跑步，但是如果a移动距离远，就抄a的作业b += 17;if (a > b) b = a;//显然，b跑的不会比a慢if (b >= s) {printf("Yes\n%d", i);return 0;}}printf("No\n%d", b);return 0;}

• 深搜

#include using namespace std;int m, s, t;//d[i]：消耗 i秒能够移动的最大距离，mint：走到终点消耗的最少时间 int d[300009], mint = 1e9;//剩下的魔法值，已经移动的距离，已经消耗的时间 void f(int mg, int dis, int tm) {if (dis < d[tm]) return;else d[tm] = dis;if (dis >= s) {//已经到达终点，递归返回 mint = min(mint, tm);return;}if (tm == t) {//未到达终点，但时间结束 return;}if (mg >= 10) {f(mg - 10, dis + 60, tm + 1);}else {f(mg + 4, dis, tm + 1);//为了优先选择使用魔法 f(mg, dis + 17, tm + 1);}}int main() {cin >> m >> s >> t;f(m, 0, 0);if (mint < 1e9) printf("Yes\n%d", mint);else printf("No\n%d", d[t]);return 0;}