自动搬运

查看原文

来自洛谷，原作者为

	linyinuo2008 **

搬运于2025-08-24 22:21:26，当前版本为作者最后更新于2021-02-11 22:21:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关键字：记忆化搜索

这是道记搜好题，看到之后决定来一发。

看到这题格子长度能达到$10^3$，心中差不多就明白这题暴搜肯定不行，虽然我还是傻傻的打了一份暴搜的代码

之所以看到这题就想到搜索，因为有如下几个特征。

• 是跟格子有关的题，所以简单算法可能种类就是动态规划，贪心，搜索，和入门无算法题。

• 有后效性，排除贪心。

• 数据范围很适合搜索，可能需要一些优化。

• 不过想到动态规划很正常，下面我们来看一下为什么动态规划做不了这题。

动态规划的想法

我们来仔细想一下这题用动归该怎样配置。

首先，我们可以先设$f_i$表示跳到第$i$个格子所需最少费用，但是这里少了一个重要的信息量：上一步跳的步数（这个变量在后面搜索时也会用到）。

于是我们设$f_{i,j}$表示当前在第$i$个格子，上一步跳了$j$个格子时的最小费用，于是易得转移方程：

$f_{i,j}$ $=$ $min(f_{i-j,j},f_{i+j+1,j+1})$ $+$ $a_i$

别忘了判断越界，其中$a_i$为当前格子花费。

答案：$min(f_{n,i})$ 其中$1 \leq i \leq n$

于是问题来了，我们应当如何枚举$i$,$j$，来完成动归转移？由于我们无法确定当前的步数，所以没有确定的转移顺序，于是动态规划差不多与这题无缘了（如果有大佬用动归做出来了请在讨论区里回复）。我们只好用分阶段递归来解决（这不就是搜索吗）。

暴搜基本思路

1. 判断是否到达终点，若到达，取当前答案与此次结果最小值，返回。

2. 判断是否越界，若越界，则返回。

3. 向$1$号格子方向搜索。

4. 向终点方向搜索。

递归函数参数：pos（当前格子），len（走到这个格子走过的距离），money（已花钱数）。

结果：TLE6个点。

What do you expect?

记忆化搜索优化开始。

记忆化搜索思路

用一个$vis$数组来记录之前是否用相同的距离到达过这个点，若到达就记录下这个点所需最小钱数。

1. 判断是否越界，若越界返回一个巨大值，卡死这条路。

2. 如果到了最后一个格子，就返回这个格子的钱数。

3. 如果当前点已被记录过，就直接返回就可以了（这就是记搜的优化精髓）。

4. 向两边继续搜记录在$vis$里，取最小值，别忘加当前格子钱数欧。

5. 返回初始点$vis$值。

递归函数参数：pos（当前格子），len（走到这个格子走过的距离）。

这里说一下为什么只用两个参数，而不用加一个代表上一步方向的变量dir。因为我们考虑的是在这一个格子往前跳到终点所花钱数，而与它上一步从哪个格子来的无关。我们考虑的只是钱数，并不关心他上一个格子的花费。

我们需要记录上一步步数是因为这与下一步走的步数有关（可能加一）。

下面上代码（有注释）：

$CodeTLE:$

#include <iostream>
using namespace std;
const int N=1001;
const int INF=0x7f7f7f;//设的大一些
int ans,n,a[N];
int min(int a,int b)
{
	return a<b?a:b;
}
void dfs(int pos,int len,int money)
//money是当前所需的钱数，pos是当前的位置，len是上次走的步数 
{
	if(pos==n)  ans=min(ans,money+a[pos]);//到达更新ans 
	if(pos<1||pos>n)  return ;//判越界 
	//两边搜 
	dfs(pos-len,len,money+a[pos]);
	dfs(pos+len+1,len+1,money+a[pos]);
	
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	ans=INF;//别忘记初始化ans为无穷大 
	dfs(2,1,0);//从第二个格子开始搜 
	cout<<ans;
	return 0;
}

$CodeAC:$

#include <iostream>
using namespace std;
const int N=1001;
//vis[pos][len]表示现在在第pos个格子，上次走了len步时所花的最少钱数 
int n,a[N],vis[N][N];
int min(int a,int b)//手动写min 
{
	return a<b?a:b;
}
int search(int pos,int len)
//pos是当前的位置，len是上次走的步数 
{
	if(pos<1||pos>n)  return 0x7f7f7f7f;//这个点好毒瘤，写0x7f都过不了 
	if(pos==n)  return a[n];//到终点返回钱数 
	if(vis[pos][len]) return vis[pos][len];//记忆化返回 
	return vis[pos][len]=min(search(pos-len,len),search(pos+len+1,len+1))+a[pos];//向两边搜 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cout<<search(2,1);//从第二个格子开始搜 
	return 0;
}

注：这题数据真不错，记搜写成0x7f一个点都过不了。

管理员大大求通过！

若有错误，欢迎指出！