袋鼠过河---DP

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

输入：输入分两行，第一行是数组长度N，第二行是每一项的值，用空格分隔；

输出：输出最少的跳数，无法到达输出-1；

样例输入

5

2 0 1 1 1

思路：定义dp[i] 表示到达i米的时候需要的最少跳，定义v[i] 表示在之前的跳中能否到达i，状态转移如下，把从当前位置能到达的桩子全计算dp[];

for(int j=i+1;j<=a[i]+i;j++)
{

    if(v[i]&&!v[j])  dp[j]=dp[i]+1,v[j]=1;

}

代码如下：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#include <set>

#include <queue>

#include <vector>

using namespace std;

int a[];

int dp[];

int v[];

int main()

{

    int N;

    while(scanf("%d",&N)!=EOF)

    {

        for(int i=;i<=N;i++)

            scanf("%d",&a[i]);

        memset(dp,,sizeof(dp));

        memset(v,,sizeof(v));

        dp[]=; v[]=;

        for(int i=;i<=+a[];i++)

        {

            dp[i]=;

            v[i]=;

        }

        for(int i=;i<=N;i++)

        {

            if(a[i]==) continue;

            for(int j=i+;j<=a[i]+i;j++)

            {

                if(v[i]&&!v[j])  dp[j]=dp[i]+,v[j]=;

            }

        }

        if(v[N+])  cout<<dp[N+]<<endl;

        else        cout<<"-1"<<endl;

    }

    return ;

}