动态规划两题浅析

动态规划两题浅析

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注