题解 P6507 【[COCI2007-2008] NIKOLA】

· · 题解

关键字：记忆化搜索

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

看到这题格子长度能达到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一个点都过不了。

管理员大大求通过！

若有错误，欢迎指出！