[NOIP2007 普及组] 守望者的逃离 题解

题意

给定 $M(0\le M\le 10^3),S(1\le S\le 10^8),T(1\le T\le 3\times 10^5)$，守望者开始在位置 $0$，对于每一秒（以下每一种操作的持续时间都是一整秒），有以下三种操作，可以选择其中一种：

• 当前位置增加 $17$，不改变 $M$。
• 当 $M\ge 10$ 时，可将当前位置增加 $60$，并将 $M$ 扣除 $10$。
• 不移动位置，并将 $M\leftarrow M+4$。

求守望者能否在 $T$ 秒内走 $S$ 个位置，如果可以，输出 Yes 和最短在第几秒后可以走超过 $S$ 个位置；否则输出 No，并输出在第 $T$ 秒最远可以走到哪里。

思路

考虑当 $M=0$ 时，如果剩余路程还很长，则可注意到对于每一次普通的走路在 $7s$ 内可以走 $119m$，用特殊操作（进行五次操作 $3$ 和两次操作 $2$ 可以将路程增加 $120m$ ），因此特殊操作的速度显然快于普通操作。

首先令 $d{p}_i$ 表示在第 $i$ 秒内最远可以走到哪：

• 当 $M\ge 10$ 时，$d{p}_i\leftarrow d{p}_{i-1}+60,M\leftarrow M-10$ 。
• 否则，$d{p}_i\leftarrow d{p}_{i-1}M\leftarrow M+4$。

此时求出的还不是第 $i$ 秒的最佳情况，毕竟你进行操作 $2$ 增加魔法值的同时通过进行操作 $1$ 肯定在第 $i$ 秒时更优，因此再次循环：

• 如果 $d{p}_i<d{p}_{i-1}+17,d{p}_i\leftarrow d{p}_{i-1}+17$

从而达到真正能求出 $d{p}_i$ 而不影响进行操作 $2,3$ 的效果。

最后进行相应判断即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,s,t,dp[300005];
signed main() {scanf("%lld %lld %lld",&m,&s,&t);for(int i = 1;i <= t;i++) {if(m >= 10) m -= 10,dp[i] = dp[i - 1] + 60;else m += 4,dp[i] = dp[i - 1];}for(int i = 1;i <= t;i++) {if(dp[i] < dp[i - 1] + 17) dp[i] = dp[i - 1] + 17;if(dp[i] >= s) {printf("Yes\n%lld",i);return 0;}}printf("No\n%lld",dp[t]);return 0;
}