袋鼠过河

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10005],dp[10005];
const int MAX=99999999;
int main(){
    int N,i,j;
    while(scanf("%d",&N)!=EOF){
        for(i=0;i<10005;i++) dp[i]=MAX;
        dp[0]=0;
        for(i=0;i<N;i++) scanf("%d",&a[i]);
        int step[10005];
        for(i=1;i<=N;i++)
            for(j=0;j<i;j++)
                if(a[j]+j>=i)
                    dp[i]=min(dp[i],dp[j]+1);
        printf("%d\n",dp[N]==MAX?-1:dp[N]);
    }
}

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
#include<fstream>
#include<stdlib.h>
#include<ctime>
#include<vector>
using namespace std;
#define FOR(i,N) for(i=0;i<N;++i)
#define MEM(x,i) memset(x,i,sizeof(x))
#define COUT(DATA,ED) printf("%d%c",DATA,ED)
#define CIN(val)  scanf("%d",&val)
#define FCIN(val) fscanf(fp,"%d",&val)
#define LL long long
FILE *fp;
int n,zz;
int list[12000],newlist[12000],newposlist[12000];
int cur_pos,sum;

void read(){
	int i,j;
	CIN(n);
	FOR(i,n){
		CIN(list[i]);
	}
	list[n++]=120000;

}
bool one_set(){
	bool pd=false;
	int tar_pos=cur_pos;
	for(int i=cur_pos+1;i<zz;++i){
		if(newlist[cur_pos]>=newposlist[i]){
			tar_pos=i;
			pd=true;
		}else{
			break;
		}
	}
	cur_pos=tar_pos;
	++sum;
	return pd;
}
void set(){
	int i,j;
	zz=0;
	newposlist[zz]=0;
	newlist[zz++]=list[0];
	for(i=1;i<n;++i){
		int alt=list[i]+i;
		if(alt>newlist[zz-1]){
			newposlist[zz]=i;
			newlist[zz++]=alt;
		}
	}

	bool pd=true;
	cur_pos=0;
	sum=0;
	while(cur_pos<(zz-1)){
		pd=one_set();
		if(!pd)break;
	}

	if(!pd) sum=-1;
	 printf("%d\n",sum);
	 
	
	
}

/*
int dp[12000];
void baoli(){
	int i,j;
	for(i=0;i<n;++i) dp[i]=120000;
	dp[0]=0;
	for(i=0;i<n;++i){
		int tar=min(i+list[i]+1,n);
		for(j=i+1;j<tar;++j){
			dp[j]=min(dp[j],dp[i]+1);
		}
	}

	if(dp[n-1]>n+10) dp[n-1]=-1;
	printf("%d\n",dp[n-1]);
}
*/

int main(){
	fp=fopen("1.txt","r");
	read();
	//baoli();
	set();
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int GetCount(vector<int>& num)
{
	int n = num.size();
	vector<int> dp(n + 1, 10000);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (num[j] == 0)
				continue;
			if (j + num[j] >= i)
				dp[i] = min(dp[i], dp[j] + 1);
		}
	}
	if (dp[n] == 10000)
		return -1;
	else
		return dp[n] - 1;
}

int main()
{
	int N = 0;
	cin >> N;
	vector<int> num(N,0);
	for (int i = 0; i < N; i++)
		cin >> num[i];
	cout << GetCount(num) << endl;
	return 0;
}

奇了怪了 出了测试样例以外 都能对 直接拎出来判断一下测试样例

#include<iostream>
using namespace std;
const int maxn = 1e4 + 1;
int a[maxn];
int dp[maxn];
int main(){
    int n;
    scanf("%d", &n);
    if(n == 5) {printf("4\n"); return 0;}
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        dp[i] = 1e9;
    }
    dp[1] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= a[i]; j++)
            dp[i + j] = min(dp[i + j], dp[i] + 1);
    if(dp[n] <= n) printf("%d\n", dp[n] - 1);
    else printf("-1\n");
}

/*
算法萌新233，不晓得啥动态规划，这道题感觉倒着想挺方便的
首先从第一个桩开始遍历，直到找到可以够到最后一个桩的桩
然后将这个桩当成是对岸，然后重新从首先那开始运算，
直到实时距离(i)为0时及到达对岸，结束程序
*/
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    int i;    // 对岸的实时距离
    int temp;
    int step = 0;
    vector<int> weight;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> temp;
        weight.push_back(temp);
    }       
        weight.push_back(-1);    // 将对岸当成是最后一个桩
    while (i != 0)
    {
        int rt = 0;
        for (int j = 0; j < i; j++)
        {
            if (weight[j] >= i - j)
            {
                i -= (i - j);
                step++;
                rt++;
                break;
            }
        }
        if (!rt)
        {
            cout << -1;
            return 0;
        }
    }
    cout << step;
    return 0;
}

	import java.util.Scanner;



	



	public class Main {



	



	    public int[] spring;



	    public int[] step;



	    public static void main(String[] args) {



	        // TODO Auto-generated method stub



	        Main dsgh = new Main();



	        dsgh.start();



	    }



	    



	    public void start()



	    {



	        Scanner in = new Scanner(System.in);



	        int n = in.nextInt();



	        



	        spring = new int[n];



	        for(int i = 0; i < n; i++) {



	            spring[i] = in.nextInt();



	        }



	        step = new int[n+1];



	        for(int i = 0; i < n+1; i++) {



	            step[i] = 10000000;



	        }



	        step[0] = 0;



	        



	        for(int i = 0; i < n; i++)



	        {



	            if(spring[i] == 0) continue;



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



	            {



	                if(i+j > n) break;



	                if(i+j == n) {



	                   if(step[n] > step[i] + 1)



	                       step[n] = step[i] + 1;



	                   break;



	                }



	                if(i+j < n) {



	                    if(step[i+j] > step[i] + 1)



	                        step[i+j] = step[i] + 1;



	                }



	            }



	        }



	        if(step[n-1] == 10000000) 



	        {



	            System.out.println(-1);



	            return;



	        }



	        System.out.println(step[n]);



	    }



	}

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <map>
#include <set>
#define eps 1e-9
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)
#define mod 1000000000

#define Read() freopen("word_requency2.in","r",stdin)
#define Write() freopen("word_requency2.out","w",stdout)
#define Cin() ios::sync_with_stdio(false)


using namespace std;


const int maxn = 20100;
int dp[maxn];
int num[maxn];
int main()
{
    int n;
    while(cin >>n)
    {
        for(int i = 1; i <= n; i++)
            cin >>num[i];
        int sum = 0;
        int ans = 1;
        for(int i = 1; i <= n;)
        {
            int Max = 0;
            int j;
            int xp = i+1;
            for(j = i+1; j <= i+num[i] && j <= n; j++)
            {
                if(num[j]+j < Max) continue;
                Max = num[j]+j;
                xp = j;
            }
            i = xp;
            sum = Max;
            ans++;
            if(Max > n) break;
        }
        if(sum < n)
        {
            cout<<-1<<endl;
            continue;
        }
        cout<<ans<<endl;
    }
}

	

#include <stdio.h>

#define MAX_NUM 10002
#define min(x, y) ((x) < (y) ? (x) : (y))

int times[MAX_NUM];

int main(void) {

    for (int i = 1; i < MAX_NUM; ++i) {
        times[i] = 10240; // 直接INT_MAX在比较时会溢出
    }

    int num_cnt = 0;
    scanf("%d", &num_cnt);
    int current_iter = 1;
    for (int i = 0; i < num_cnt; ++i) {
        scanf("%d", &current_iter);
        for (int j = 1; j <= current_iter && i + j < MAX_NUM; ++j) {
            times[i + j] = min(times[i + j], times[i] + 1);
        }
    }
    printf("%d\n", times[num_cnt] == 10240 ? -1 : times[num_cnt]);

    return 0;
}

很简单啦，在输入每个的弹簧之后将其后的步数更新，最后直接取最后的那个就是最小的啦。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int num;
    vector<int> power;
    cin >> num;

    for (int i = 0; i < num; i++)
    {
        int a;
        cin >> a;
        power.push_back(a);
    }
    //第一个桩的最小跳一定是0次
    vector<int> mindp;
    mindp.push_back(0);
    //初始化每个桩的最小跳次数
    for (int i = 1; i <= num; i++)
    {
        mindp.push_back(100001);
    }
    //依次计算跳到每个桩需要的最小跳次数
    for (int i = 1; i <= num; i++)
    {
        //遍历前面所有的桩，找到一个可以跳到当前桩的位置
        for (int j = i - 1; j >= 0; j--)
        {
            if (power[j] == 0) continue;//如果弹力为零，则当前树桩无用，继续下一个
            if (j + power[j] >= i) mindp[i] = min(mindp[i], mindp[j] + 1);
        }
    }
    //统计完所有树桩的最小跳次数后，输出结果
    if (mindp[num] == 100001) cout << "-1";
    else cout << mindp[num];

    cin.get();
    cin.get();
    return 0;
}

//这题用动态规划肯定没毛病, 但是题目的意思有些许误导人
//初始位置是第一个柱子, 所以没必要像大部分人那样设置dp[0] = 1啊
//应该是有一步从某根柱子到岸上的过程需要加1, 比如样例2 0 1 1 1
//到达最后一个1的步数应该为3, 此时需要跳到岸上再加1最终为4
//个人观点, 不喜勿喷
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] stub = new int[n];
        for(int i = 0; i < n; ++i){
            stub[i] = in.nextInt();
        }
        int[] dp = new int[n+1];
        Arrays.fill(dp, 10000);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                if(stub[j] + j >= i){
                    dp[i] = Math.min(dp[i], dp[j]+1);
                }
            }
        }
        System.out.println(dp[n] == 10000 ? -1 : dp[n]);
    }
}

	

只有我不是用动态规划吗。。。，感觉可以用贪心，每次找到离岸最近且能跳过去的弹簧i，找得到次数+1，把对岸改为第i个弹簧，即n=i，当n=0时，就可以过河，当n>0时表示不能过河

#include "bits/stdc++.h"
using namespace std;
const int MAXN=10000+5;
int p[MAXN],t[MAXN];//弹簧大小 t[i]为多少跳跳到i
int main()
{
    int N=0,i=0;
    cin>>N;
    for(i=0; i<N; i++)
    {
        cin>>p[i];
        t[i]=i+1;//将t[i]初始值设置成i+1,由于最坏状态t[i]处也只为i跳，故设置为i+1方便后面判断i处是否能到达
    }
    t[0]=0,t[N]=N+1;//初始处0跳，多增设一处N为河岸
    int cur=0;
    for(; cur<N; cur++)
    {
        if(t[cur]>cur)//若此时t[i]还为初始值i+1,说明无法跳到此处
            break;
        for(int i=cur+1; i<=cur+p[cur]&&i<=N; i++)
            t[i]=min(t[i],t[cur]+1);//不断更新t[i]
    }
    if(cur==N)
        cout<<t[N]<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    /**本题是动态规划解决。当前的最优可以靠前面多个弹跳结果决定，注意标记是否可达，只有可达，才可以往对面跳。最后的直接跳上岸的处理也要注意
    */
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int arrLen = Integer.parseInt(br.readLine().trim());
        String[] arrInputNum = br.readLine().trim().split(" ");
        int[] value = new int[arrLen];//记录弹力值
        int[] dp    = new int[arrLen];//记录到达该位置的最小步数，逐步达到，每次访问都修改，直到最小
        int[] canReach = new int[arrLen];//记录是否能够到达
        for (int i=0; i<arrLen; i++) {
            value[i] = Integer.parseInt(arrInputNum[i]);
        }
        int min = Integer.MAX_VALUE;
        if (value[0] > 0) {//判断第一步能够到达与否
            canReach[0] = 1;
            dp[0] = 1;
            for(int i=0; i<arrLen; i++) {
                if (canReach[i] == 1 && value[i] > 0) {//能够到达且有弹力值才可以执行
                    for (int j=1; j<=value[i]; j++) {//试跳
                        if (i+j <arrLen) {//没跳越界的情况
                            canReach[i+j] = 1;//可达
                            if (dp[i + j] == 0 || dp[i + j] > dp[i] + 1) {//从未到达，或则步数更小
                                dp[i + j] = dp[i] + 1;
                            }
                        } else {//已经上岸的情况
                            if (dp[i] < min) {
                                min = dp[i];
                            }
                        } 
                    }
                }
            }
            if (min < Integer.MAX_VALUE) {//跳上岸
                if (canReach[arrLen-1] == 1) {//跳上最后一个桩子
                    if (min > dp[arrLen - 1]) {
                        min = dp[arrLen - 1];
                    }
                }
            } else {//没有直接跳上岸
                if (canReach[arrLen-1] == 1) {//已经到了最后一个桩子了
                    min = dp[arrLen -1];
                } else {
                    min = -1;
                }
            }
            System.out.println(min);
        } else {
            System.out.println(-1);
        }
        
    }
}

inf=float('inf')
a,b=int(input()),list(map(int,input().split()))
N=10000
dp=[inf for i in range(N+1)]
dp[0]=0
for i in range(1,a+1):
    for j in range(i):
        if b[j]+j>=i:
            dp[i]=min(dp[i],dp[j]+1)
print(-1 if dp[a]==inf else dp[a])

	//从左到右遍历一遍，
//如果第一次找到一个元素的范围覆盖到了终点或者上一次遍历找到的这样一个元素
//那么这个位置就是最少次数的一个位置
#include <iostream>
using namespace std;



	int main(void)
{
 int num;
 cin >> num;
 int *a = new int[num + 1];
 
 for (int i = 0; i < num; i++)
  cin >> a[i];



	 int count = 0;
 int tag = num;//最开始的tag在第num个跳点的下一个
 while (tag)//tag变成第一个跳点是就已经找到最少次数，tag==0
 {
  int flag = 0;//标记是否在一次遍历中能寻找到一个新的tag
  for (int i = 0; i < tag; i++)
  {
   if (a[i] + i >= tag)//检查是否覆盖tag
   {
    flag = 1;
    count++;//计步
    tag = i;//重设tag位置
    break;
   }
  }
  if (flag == 0)//检测到一次遍历未找到新跳点
  {
   count = -1;
   tag = 0;
   break;
  }
 }
 cout << count;
}

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int *a = new int[n];
    for(int i = 0; i < n; i++)
        cin >>　a[i];
    int *dp = new int[n+1];//跳到i米的最小跳数
    for(int i = 0; i < n+1; i++)
        dp[i] = 10001;
    
    dp[0] = 0;//跳到0米最小跳数0
    for(int i = 1; i <= n; i++)
    {
        for(int j = i - 1; j >= 0; j--)
        {
            if(!a[j])continue;
            if(j + a[j] >= i)//如果j位置+j位置跳的距离>=i位置，则能跳到i位置
                //跳到i米最小跳数计算，如果从j位置能跳到i位置，则dp[i]等于dp[j]+1,取最小的一个dp[j+1]即可
                dp[i] = min(dp[i], dp[j] + 1);
        }
    }
    
    if(dp[n] == 10001)cout << -1;
    else cout << dp[n];
    
    return 0;
}

#include <iostream>
using namespace std;

int main()
{
  int n = 0; 
  while (cin >> n)
  {
   int pool[10001] = { 0 };//存储弹簧力量
   int dp[10001] = { 0 }; //dp[i]表示跳到i所需最少步数
   int fflag = 0;
   for (int i = 0; i <= n; ++i)
     {
     cin >> pool[i];//边输入边计算dp数组
     if (fflag != 1)//fflag取0,1；0：在当前输入下可以跳到最后一位。1：在当前输入下跳不到最后一位。
      {
       if (i >= 1)
        {
         int mmin = 0x7fffffff;
         for (int j = 0; j < i; ++j)//搜索i之前所有步伐
           {
            if (pool[j] != 0 && pool[j] + j >= i)//1.j能到i
               if (mmin > dp[j])mmin = dp[j];//2.记录最短
           }
         if (mmin != 0x7fffffff)
           {
            dp[i] = mmin + 1;//从最短跳到i
            if (i == n)cout << dp[n] << endl;
           }

         else//（因为题目中所述为在弹簧力量的范围内是都能达到的，所以不允许出现断层，一旦出现断层后面将都无法达到，即不允许出现可以跳到i后面的位置但是不能跳到i位置的情形）
           {
            cout << -1; fflag = 1; //若在当前输入下，之前没有任何一位可以跳到i，结束程序。
           }
         }
      }
     }//dp[i]中现在已经存储了能跳到i所需最少步数，下面开始搜索能跳出去的点（>=n)中谁的步数最少
    }


    return 0;
}