Q1 [AtCoder-4522]

有一蛙，立于1号岩石上，目标是要跳到N号石头上，每次它可以跳到前边一块或隔一块。两石头的高度差的绝对值是青蛙每次跳跃的代价，试问青蛙到终点时可以消耗的最小代价值为多少

解析

动规一般从小规模开始算，假设蛙在第N-1的石头上，只有1种跳法，即代价为cost[N-1]=abs(h[N-1]-h[N])，而当他在第N-2块石头上，它就可以选择直接跳，或跳到N-1上再花费cost[N-1]，所以cost[N-2]等于abs(h[N-2]-h[N])与 abs(h[N-2]-h[N-1])+cost[N-1]的较小值，归纳得到当它在第i块岩石上的时候，它的跳到终点的代价为min( abs(h[i]-h[i+2])+cost[i+2],
abs(h[i]-h[i+1]) +cost[i+1]) ，使i从N-1遍历到0，输出cost[1]即为青蛙从第1号岩石到第N号岩石的最小代价

#include <cstdio>
#include <algorithm>
using std::min;
int m_abs(int z)
{
    if (z<0)
        return -z;
    else
        return z;
}
int main(void)
{
    int *a,*dp,N,i,j;
    scanf("%d",&N);
    a=new int [N];
    dp=new int [N];
    for (i=0;i<N;i++)
    {
        scanf("%d",a+i);
    }
    dp[N-1]=0;
    dp[N-2]=abs(a[N-2]-a[N-1]);
    for(i=N-3;i>=0;i--)
    {
        dp[i]=min(dp[i+1]+abs(a[i]-a[i+1]),dp[i+2]+abs(a[i]-a[i+2]));
    }
    printf("%d\n",dp[0]);
    delete [] a;
}

Q2 [AtCoder-4523]

有一只更强的蛙，立于1号岩石之上，它的目标是跳到N号岩石上，假定当前脚下的编号为i，它可以跳到编号为i+1,i+2,…,i+K的岩石上(Q1即是此处K=2的情形)，跳跃代价为两岩石的高度之差，计算青蛙到终点的最小代价

分析

与Q1类似，仍应从N-1,N-2,…N-k开始计算，N-1只有1种跳法，N-2有两种跳法，在N-1确定的情况下N-2也可确定，以此推算出N-k的代价。再往前若青蛙站在了一次跳不到终点的地方，就去看它接下来可跳的K个岩石的代价与从这个岩石跳到那边的代价之和的最小值，算到cost[1]即它从第1号岩石上所使用的最小代价

#include <cstdio>
#include <algorithm>
using std::min;
int m_abs(int z)
{
    if (z<0)
        return -z;
    else
        return z;
}
int main(void)
{
    int *a,*dp,N,i,j,K;
    scanf("%d%d",&N,&K);
    a=new int [N];
    dp=new int [N];
    for (i=0;i<N;i++)
    {
        scanf("%d",a+i);
    }
    dp[N-1]=0;
    if(K>N)
        K=N;
    for(i=0;i<K;i++)
        dp[N-1-i]=abs(a[N-1]-a[N-1-i]);
    for(i=N-1-K;i>=0;i--)
    {
        dp[i]=dp[i+1]+abs(a[i]-a[i+1]);
        for(j=2;j<=K;j++)
        {
            dp[i]=min(dp[i+j]+abs(a[i]-a[i+j]),dp[i]);
        }
        //printf("dp[%d]= %d\n",i,dp[i]);
    }
    printf("%d\n",dp[0]);
    delete [] dp;
    delete [] a;
    return 0;
}