袋鼠过河---DP

时间:2021-01-23 00:30:22

题目:一只袋鼠要从河这边跳到河对岸,河很宽,但是河中间打了很多桩子,每隔一米就有一个,每个桩子上都有一个弹簧,袋鼠跳到弹簧上就可以跳的更远,每个弹簧力量不同,用一个数字代表它的力量,如果弹簧力量为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 ;
}