原题传送门

这道题要用到压缩的思想(原来DP还能这么用。。。)

其实很简单,假如我们要到某一个位置w

如果我们原位置为Q

很显然,如果(W-Q>=s*t)那么我们一定能到达W

换言之,就是如果我们我们可以到达s*t+1~s*t+t的任意位置

然后我们就可以取膜啦

每次最多只能前进100格,100次后只能前进10000格

那么就可以DP啦,是不是很神奇?

但是我们要考虑一种特殊情况,如果s=t,那么上述方法是没有任何效果的。

所以我们只能到达s倍数的点

所以要特殊处理咯

下面贴代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define min(a,b) (a)<(b)?(a):(b)
using namespace std;
int num[];
bool stone[];
int dp[];
int ans=,l,s,t,m;
int main(){
scanf("%d%d%d%d",&l,&s,&t,&m);
for(int i=;i<=m;i++)scanf("%d",&num[i]);
num[]=;num[m+]=l;
sort(num+,num+m+);
if(s==t)
{
int tot=;
for(int i=;i<=m;i++)
if(!(num[i]%s))tot++;
printf("%d\n",tot);
}
else{
int k=s*t,move=;
for(int i=;i<=m+;i++)
{
int x=num[i]-move-num[i-];
if(x>k)move+=x-k;
num[i]-=move;
stone[num[i]]=true;
}
stone[num[m+]]=false;
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=num[m+]+t-;i++)
{
for(int j=s;j<=t;j++)
if(i>=j)dp[i]=min(dp[i],dp[i-j]);
dp[i]+=stone[i];
}
for(int i=num[m+];i<=num[m+]+t-;i++)
ans=min(ans,dp[i]);
printf("%d\n",ans);
}
}

最新文章

  1. windo phone8.1 样式的基本使用(一)
  2. HBase自动分区
  3. VBS实现定时发送邮件
  4. Linux摄像头驱动学习之:(六)UVC-基本框架代码分析
  5. IOS UITableView下拉刷新和上拉加载功能的实现
  6. Jenkins Maven打包出错异常的解决方法
  7. 使用JDBC对数据库实现批处理操作
  8. Mysql彻底卸载
  9. 关于CSS格式与布局中的基础知识的简单操作
  10. 【一天一道LeetCode】#223. Rectangle Area
  11. 自定义用户认证(继承django的)
  12. BeTa阶段Day4
  13. Spring 装配Bean入门级
  14. window.open完美替代window.showModalDialog
  15. SaltStack配置管理--状态间的关系(六)
  16. Java集合排序
  17. ps命令查看进程指定项目信息、用户名过长显示UID
  18. leetcode:Median of Two Sorted Arrays分析和实现
  19. 11、C内存四区模型
  20. JfreeChart折线图 CSDN-李鹏飞

热门文章

  1. @ApiModelProperty用法
  2. Postgres主备切换
  3. python-13常用内建模块
  4. python协程和IO多路复用
  5. unity值得推荐的网址
  6. try-catch-finally容易犯的错误
  7. leetcode 208. 实现 Trie (前缀树)
  8. shell中的&gt;&amp;1和 &gt;&amp;2是什么意思?
  9. MVC学习笔记---WebViewPage(nop等开源项目的@T)
  10. Thymeleaf 模板 在spring boot 中的引用和应用