传送门

普及组的题目……很水。

原来写了一个模拟不过好像状态考虑的不全得了80,这次我们考虑一下dp做法。

守卫者有两种移动的方法,一种是闪现,一种是跑,我们可以把闪现和跑分开处理。

首先只处理闪现的情况,这个时候要用贪心,能闪就闪,否则原地回蓝即可。

之后在处理跑步的情况,这种情况就要用dp了,方程很好推,就是dp[i] = max(dp[i],dp[i-1]+17)

这样的做法为什么正确呢?因为其实我们跑步的时候只是会把原来只用闪现的情况中,有一些不够好的情况替换掉了,这样就能保证全部被考虑到。

看一下代码。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rep(i,a,n) for(ll i = a;i <= n;i++)
#define per(i,n,a) for(ll i = n;i >= a;i--)
#define enter putchar('\n') using namespace std;
const int M = ;
typedef long long ll; int read()
{
int ans = ,op = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-') op = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
ans *= ;
ans += ch - '';
ch = getchar();
}
return ans * op;
}
int m,s,t,dp[M];
int main()
{
m = read(),s = read(),t = read();
rep(i,,t)
{
if(m >= ) m -= ,dp[i] = dp[i-] + ;
else dp[i] = dp[i-],m += ;
}
rep(i,,t)
{
dp[i] = max(dp[i],dp[i-]+);
if(dp[i] >= s)
{
printf("Yes\n%d\n",i);
return ;
}
}
printf("No\n%d\n",dp[t]);
return ;
}

最新文章

  1. Java处理 文件复制
  2. kail linux 虚拟机安装实录(一) 新建虚拟机
  3. css3箭头效果
  4. bzoj4518: [Sdoi2016]征途--斜率DP
  5. ruby学习总结02
  6. 火车车次查询-余票查询--Api接口
  7. HDU 1084 - ACM
  8. win7下怎样设置putty免用户名密码登陆
  9. php 启动过程 - reqeust RSHUTDOWN 过程
  10. HotSpot的算法实现
  11. nodejs模块学习: connect2解析
  12. git简单提交操作
  13. IntelliJ IDEA配置Maven
  14. Log4j分级别保存日志到单个文件中,并记录IP和用户信息
  15. 洛谷P2120 [ZJOI2007]仓库建设 斜率优化DP
  16. Redis 教程 Java工程师学习知识点
  17. mysql ANSI_QUOTES 这个sql_mode的作用(字段可以使用双引号)
  18. Facebook ads_Business Manager
  19. 在Hanlp词典手动添加未登录词的方式介绍
  20. 对json数据key进行替换

热门文章

  1. Linux 的信号和线程
  2. 学习技术的三部曲:WHAT、HOW、WHY
  3. ZOJ - 4020 Traffic Light (BFS)
  4. CODEVS 1245 最小的N个和 堆+排序
  5. HSSF生成excel文件损坏
  6. go语言学习之路四:字典
  7. cms完整视频教程+源码 孔浩老师 全131讲
  8. Sentinel实现Redis高可用
  9. table合并单元格
  10. win10 UWP 申请微软开发人员