[NOIP 2007 普及组] 守望者的逃离

知识点

贪心、动态规划、策略重排

解题思路

先计算只允许闪烁与休息时每秒的最远距离：魔法够10就闪烁，否则休息恢复4。再用dp[t]=max(闪烁休息最远[t],dp[t-1]+17)加入跑步选项。按时间扫描，首次距离≥S就输出Yes和时间；否则输出No及T秒最远距离。

正确性说明

对固定闪烁次数，跑步不改变魔法，可以把所有跑步移到闪烁休息计划之后，距离和总时间不变。只含闪烁休息时，给定t最多能用k=min(t,floor((M+4t)/14))次闪烁，贪心会达到此计数。任一最优方案因此是某个闪烁休息前段加跑步后段，递推恰好对全部分界取最大。逐秒第一次达标就是最短逃离时间。

易错点

跑步不能同时恢复魔法；未逃离要输出最远距离而非用时；恢复魔法的秒数也占用总时间。

复杂度

时间O(T)，空间O(T)，可进一步滚动优化。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int M,S,T;cin>>M>>S>>T;vector<int>d(T+1);int mana=M;for(int t=1;t<=T;t++){d[t]=d[t-1];if(mana>=10)mana-=10,d[t]+=60;else mana+=4;}for(int t=1;t<=T;t++){d[t]=max(d[t],d[t-1]+17);if(d[t]>=S){cout<<"Yes\n"<<t<<'\n';return 0;}}cout<<"No\n"<<d[T]<<'\n';}