题解 P1929 【迷之阶梯】

· · 题解

//其实不太理解为什么我们老师把他当BFS练习题，汗……

这题的n^3的dp还是很容易想到的。设f[i]为到达第i个阶梯所需要的最少步数，可以从一下状态转移来：

  1. f[i-1]+1 (a[i-1]+1==a[i])

  2. f[j]+j-k+1 (a[k]+2^(j-k)>=a[i[, 1<=j<i, 1<=k<j)

第一个方程应该很好理解就是直接跳，第二个中的j表示从第j的阶梯跳到第i个阶梯，k表示从j后退k步，方程应该也很好理解，按照题意来就行了。

初始化是f[1]=0,f[i]=inf(2<=j<=n)，最后的答案就是f[n]啦

时间复杂度为O(n^3)，是可以通过的。

一道很好的线性动态规划基础练习题，当然看到题解貌似有n^2的做法也不知道是乱搞还是正解什么的……也希望看到有写BFS的同学在题解区发言QwQ

下面贴代码。由于上面思路应该讲的差不多了，所以代码就没有注释了。

#include<cstdio>
#include<cstring>
#define Min(x,y) (x<y?x:y)
const int N=206;
int a[N],n,f[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(f,0x3f,sizeof(f));
    int oo=f[0];
    f[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=a[i-1]+1) f[i]=f[i-1]+1;
        for(int j=i-1;j>0;j--)
            for(int k=j-1;k>0;k--)
                if((1<<(j-k))+a[k]>=a[i]) f[i]=Min(f[i],f[j]+j-k+1);
    }
    printf("%d\n",f[n]>=oo?-1:f[n]);
}