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