解题思路:
首先DP的套路就是先找状态
这题也找不出其他的状态了,只有时间一个
所以用f[i]表示时刻i能走多远
而仔细一想实际上决策只有跑、闪现、停三种决策
然而闪现的耗蓝要和跑步一同计算十分麻烦
于是把它们分开算:
先算闪现的,有以下框架
for i in range(1,t)
如果蓝量够
闪现,耗蓝
如果不够
停下,回蓝
接下来算走路,其实走路的只要维护之前算出的即可
因为之前已经算了只用闪现走多远,那么只要判断如果这一秒不闪或者不停(因为跑步不耗蓝)是否比之前更优即可
框架 for i in range(1,t)
如果这一秒走路比只闪现更优
那就走路,用走路替代闪现或停
同时,如果f[i]已经大于等于s,即逃出去了,那么输出并退出程序
转移方程:其实这题没什么转移方程,它不是传统DP所以没有传统的转移方程,只能说有点像基于时间轴的DP
注意事项:无
参考代码:
#include<cstdio>
const int maxt=300000+50;
using namespace std;
long f[maxt+1],m,s,t;
int main()
{
scanf("%d %d %d",&m,&s,&t);//读入
f[0]=0;
for (int i=1;i<=t;++i)
if (m>=10)//蓝量够
{
f[i]=f[i-1]+60;//闪现
m-=10;//耗蓝
}
else//缺蓝
{
f[i]=f[i-1];//原地休息
m+=4;//回蓝
}
for (int i=1;i<=t;++i)//迭代一遍,如果走路更优那么走路
{
if (f[i]<f[i-1]+17) f[i]=f[i-1]+17;//选走路
if (f[i]>=s)//到了
{
printf("Yes\n%d",i);//输出
return 0;//直接退出程序
}
}
printf("No\n%d",f[t]);//必定无解(有解的在循环中已经退了)
return 0;
}
0.0分
0 人评分
简单的a+b (C语言代码)浏览:643 |
妹子杀手的故事 (C语言代码)浏览:680 |
C语言训练-数字母 (C语言代码)浏览:584 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:611 |
小明A+B (C语言代码)浏览:1247 |
A+B for Input-Output Practice (V) (C语言代码)浏览:617 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1146 |
【明明的随机数】 (C语言代码)浏览:785 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:561 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:404 |