专栏文章
题解:P1052 [NOIP 2005 提高组] 过河
P1052题解参与者 6已保存评论 11
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @miqcehon
- 此快照首次捕获于
- 2025/12/04 02:30 3 个月前
- 此快照最后确认于
- 2025/12/04 02:30 3 个月前
P1052 [NOIP 2005 提高组] 过河 题解
Part 1:题目解法
step 1:读懂题意
青蛙尽量不要跳到石头上,但是在有些情况下无法避免不跳上去一个石头,本题需要输出这些无法避免的石头数的最小值。
step 2:思考算法
本题要用什么算法呢?显然是动态规划,我们初步的想法一定是:遍历 到 每个点,对于第 个点,我们把可以影响这个点的值的
dp[i-t] 至 dp[i-s] 取最小值,用 is_stone 数组表示一点是否有石头, 从 到 循环,于是状态转移方程就是 dp[i]=dp[i-j]+is_stone[i]。step 3:优化算法以及检查算法是否可行
但是本题的 在 以内,开一个长度为 的数组会炸空间,于是最直接的优化空间的方式就是缩点:
-
缩,因为 是 ,所以从任意点不管走几步都可以到 ,所以如果前方 长度内无石头,就可以将终点往前缩 。
可以提前预处理一下,把该缩的点缩了,把该缩的点缩了。注意特判 的情况。
Part 2:Code
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 4000005;
ll dp[M],s,t,len,truelen,m,stone[M],dis[M],is_stone[M];
int main(){
memset(dp,0x3f,sizeof(dp));
memset(dis,0x3f,sizeof(dis));
dp[0]=0; //长度为0时表示起点=终点,答案为0
cin>>len>>s>>t>>m;
for(ll i=1;i<=m;i++) cin>>stone[i];
sort(stone+1,stone+m+1); //先按石头先后排序,因为题目没有保证输入时按顺序
if(s==t){ //特判s=t的情况,如果stone[i]%s==0,说明走这一步时必须跳到第i个石头上
ll sum=0;
for(ll i=1;i<=m;i++){
if(stone[i]%s==0) ++sum;
}
cout<<sum;
return 0;
}
dis[m+1]=min(400LL,len-stone[m]); //写400LL表示把400转成 long long 类型,否则无法与 long long 类型取最小值
for(ll i=1;i<=m;i++){
dis[i]=min(stone[i]-stone[i-1],400LL);//如果距离太长就缩点
truelen+=dis[i];
is_stone[truelen]=1;
} //truelen是缩点后的长度
len+=dis[m+1];
for(ll i=1;i<truelen+10;i++){
for(ll j=s;j<=t;j++){
if(i-j>=0) dp[i]=min(dp[i],dp[i-j]+is_stone[i]); //i-j>=0 判断 i>=j 的情况,避免减成负数RE
}
}
ll ans=M*10; //赋较大初始值
for(ll i=truelen;i<truelen+10;i++){ //因为青蛙最多跳到终点位置+10,减去终点自己,就是从truelen到truelen+9可能为答案,把这些候选取最小值就是最终答案
ans=min(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}
完结撒花!
相关推荐
评论
共 11 条评论,欢迎与作者交流。
正在加载评论...