题目链接

题目描述
一只袋鼠要从河这边跳到河对岸,河很宽,但是河中间打了很多桩子,每隔一米就有一个,每个桩子上都有一个弹簧,袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同,用一个数字代表它的力量,如果弹簧力量为5,就代表袋鼠下一跳最多能够跳5米,如果为0,就会陷进去无法继续跳跃。河流一共N米宽,袋鼠初始位置就在第一个弹簧上面,要跳到最后一个弹簧之后就算过河了,给定每个弹簧的力量,求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define FOR(I,N) for(int i=0;i<n;++i)
#define min(x,y) (x<y?x:y)
const int maxn = 1e4+5;
#define INF 1<<30
int arr[maxn];
int dp[maxn];
int main()
{
    int n,flag;
    while(cin>>n)
    {
        FOR(I,N) cin>>arr[i];
        for(int i=0;i<=n;++i)
        {
            dp[i]=INF;
        }
        dp[0]=1;
        flag=1;
        FOR(I,N)
        {
            if(dp[i]==INF)
            {
                flag=0;
                break;
            }
            for(int j=i+1;j<=i+arr[i];++j)
            {
                dp[j]=min(dp[i]+1,dp[j]);
                /*
                cout<<i<<endl; 
                FOR(I,N) 
                {
                    cout<<dp[i]<<" ";
                } 
                cout<<endl;
                */
            }
        }
        if(flag) cout<<dp[n]-1<<endl;
        else cout<<"-1"<<endl;
    }
    return 0;
}
Last modification:September 21st, 2019 at 12:48 am
如果觉得我的文章对你有用,请随意赞赏