专栏文章

题解: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:思考算法

本题要用什么算法呢?显然是动态规划,我们初步的想法一定是:遍历 11LL 每个点,对于第 ii 个点,我们把可以影响这个点的值的 dp[i-t]dp[i-s] 取最小值,用 is_stone 数组表示一点是否有石头,jjttss 循环,于是状态转移方程就是 dp[i]=dp[i-j]+is_stone[i]

step 3:优化算法以及检查算法是否可行

但是本题的 LL10910^9 以内,开一个长度为 10910^9 的数组会炸空间,于是最直接的优化空间的方式就是缩点:
  • 25202520 缩,因为 25202520lcm(1,…,10)\operatorname{lcm(1,\ldots,10)},所以从任意点不管走几步都可以到 25202520,所以如果前方 25202520 长度内无石头,就可以将终点往前缩 25202520
  • 7171 缩,1101\sim10 最大不能表示的数是 7171 (原因见 [NOIP2017 提高组] 小凯的疑惑) ,所以如果前方 7171 长度内无石头,就可以将终点往前缩 7171
可以提前预处理一下,把该缩的点缩了,把该缩的点缩了。注意特判 s=ts=t 的情况。

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 条评论,欢迎与作者交流。

正在加载评论...