SH6. 袋鼠过河
描述
一只袋鼠要从河这边跳到河对岸,河很宽,但是河中间打了很多桩子,每隔一米就有一个,每个桩子上都有一个弹簧,袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同,用一个数字代表它的力量,如果弹簧力量为5,就代表袋鼠下一跳最多能够跳5米,如果为0,就会陷进去无法继续跳跃。河流一共N米宽,袋鼠初始位置就在第一个弹簧上面,要跳到最后一个弹簧之后就算过河了,给定每个弹簧的力量,求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1输入描述
输入分两行,第一行是数组长度N (1 ≤ N ≤ 10000),第二行是每一项的值,用空格分隔。输出描述
输出最少的跳数,无法到达输出-1示例1
输入:
5 2 0 1 1 1
输出:
4
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-10-25
#include<iostream> using namespace std; const int n=1000; int main(){ int N,i,j=0; int step=0; cin>>N; int *s=new int[N]; for(i=0;i<N;i++){ cin>>s[i]; } for(i=0;i<N;i++){ if(s[i]>=N-i){ ++step; N=i; i=-1; } } if(N!=0) { cout<<-1; } else cout<<step; delete []s; return 0; }
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-10-18
#include<iostream> using namespace std; const int n=1000; int main(){ int N,i,j=0; int step=0; cin>>N; int *s=new int[N]; for(i=0;i<N;i++){ cin>>s[i]; } for(i=0;i<N;i++){ if(s[i]>=N-i){ ++step; N=i; i=-1; } } if(N!=0) { cout<<-1; } else cout<<step; delete []s; return 0; }
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-09-21
#include<iostream> using namespace std; int main() { int n, a[10000],i; cin >> n; for ( i = 0; i < n; i++) { cin >> a[i]; } int count = 0; for ( i = 0; i < n; i++) { if (a[i]>=n-i) { count++; n = i;i = -1; } } if (n!=0) { cout << -1; } else cout << count; return 0; }
C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-30
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; int temp; vector<int> vec; vector<int> result; cin>>n; for(int i=0; i<n; i++) { cin>>temp; vec.push_back(temp); result.push_back(10000); } result.push_back(10000); result[0]=0; for(int i=0; i<n; i++) { if(vec[i]==0) continue; for(int j=0; j<i; j++) { if(vec[j]>=(i-j)) result[i] = min(result[j]+1, result[i]); } } for(int j=0; j<n; j++) { if(vec[j]>=(n-j)) result[n] = min(result[j]+1, result[n]); } if(result[n]==10000) result[n]=-1; cout<<result[n]<<endl; return 0; }
C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-24
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin>>n; int i,j,a[n]; for (i=0;i<n;i++) cin>>a[i]; vector<int> dp(1005); // int dp[1005]={0}; dp[0]=0; if (a[0]>=1) dp[1]=1; else { cout<<-1<<endl; return 0; } for (i=2;i<=n;i++) { int minnum=n+1; for (j=0;j<=i-1;j++) if (a[j]>=i-j) { int cur=dp[j]+1; if (cur<minnum) minnum=cur; // minnum=min(minnum,dp[j]+1); } dp[i]=minnum; } if (dp[n]==n+1) { cout<<-1<<endl; return 0; } else cout<<dp[n]<<endl; return 0; }