DP27. 跳跃游戏(二)
描述
输入描述
输出描述
输出能获得的最多的积分示例1
输入:
6 2 4 2 1 0 100
输出:
106
说明:
首先位于nums[0]=2,然后可以跳1步,到nums[1]=4的位置,积分=2+4=6,再跳到nums[5]=100的位置,积分=6+100=106示例2
输入:
6 2 4 0 2 0 100
输出:
108
说明:
跳跃路径为:2=>4=>2=>100,总共为108示例3
输入:
6 2 3 2 1 0 100
输出:
-1
说明:
跳不到最后一个位置,返回-1C 解法, 执行用时: 14ms, 内存消耗: 1048KB, 提交时间: 2022-02-27
#include<stdio.h> #define max(a,b) (a>b?a:b) int a[100000]; int dp[100000]; int main() { int n,t; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } dp[0]=a[0]; if(n==0) { printf("-1"); return 0; } if(n==1) { printf("%d",a[n-1]); return 0; } for(int i=1;i<n;i++) { if(i<=t) { t=max(t,i+a[i]); for(int j=i-1;j>=0;j--) { if(j+a[j]>=i) { dp[i]=a[i]+dp[j]; break; } } } if(i>t) { printf("-1"); return 0; } } printf("%d",dp[n-1]); }
C++ 解法, 执行用时: 14ms, 内存消耗: 1752KB, 提交时间: 2022-07-21
#include <bits/stdc++.h> // C++万能头文件 using namespace std; static const auto io_sync_off = [](){ // lambda表达式 std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步 std::cin.tie(nullptr); // 解除cin和cout的绑定 return nullptr; }(); int main() { int n; cin >> n; if (n == 0) { cout << "-1\n"; return 0; } int nums[n], dp[n]; // dp[i]为到达i的最大得分 memset(dp, -1, sizeof(dp)); for (int i = 0; i < n; ++i) cin >> nums[i]; dp[0] = nums[0]; for (int i = 1; i < n; ++i) { for (int j = i - 1; j >= 0; --j) { if (dp[j] != -1 && j + nums[j] >= i) { dp[i] = max(dp[i], dp[j] + nums[i]); break; // 从过去最大得分处跳跃而来,不用继续遍历了 } } if (dp[i] == -1) { // 没有能从过去跳跃而来的点 cout << "-1\n"; return 0; } } cout << dp[n - 1] << "\n"; return 0; }
C++ 解法, 执行用时: 15ms, 内存消耗: 1164KB, 提交时间: 2022-04-20
#include <bits/stdc++.h> using namespace std; int fun(vector<int>& v) { vector<int> dp(v.size(), -1); dp[0] = v[0]; for (int i = 1; i < dp.size(); ++i) { for (int j = i-1; j >= 0; --j) { if (dp[j] != -1 && v[j]+j >= i) { dp[i] = max(dp[i], v[i]+dp[j]); break; } } if (dp[i] == -1) { break; } } return dp.back(); } int main() { ios::sync_with_stdio(false); int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; ++i) { cin >> v[i]; } cout << fun(v) << endl; return 0; }
C++ 解法, 执行用时: 15ms, 内存消耗: 1716KB, 提交时间: 2022-02-17
#include <bits/stdc++.h> #define rep(i,a,b) for(int i = (a); i < (b); ++i) #define ms(a,b) memset(a,b,sizeof(a)) using namespace std; typedef pair<int,int> P; const int MAXN = 2e5 + 10; int a[MAXN]; int dp[MAXN] = {0}; int main(){ ios::sync_with_stdio(0); int n; cin >> n; if(n==0){ cout << -1 << endl; return 0; } rep(i,0,n) cin >> a[i]; dp[0] = a[0]; rep(i,1,n){ //rep(j,0,i){ // 不要从左往右数 for(int j=i-1;j>=0;j--){ if(dp[j] && j+a[j]>=i){ dp[i] = dp[j]+a[i]; break; } } //如果最远连i都到不了,i+1肯定也到不了 if(!dp[i]) break; } cout << (dp[n-1]?dp[n-1]:-1) << endl; return 0; }
Go 解法, 执行用时: 15ms, 内存消耗: 5968KB, 提交时间: 2022-03-07
package main import ( "bufio" "os" "strings" "strconv" "fmt" ) func main(){ br:=bufio.NewReader(os.Stdin) str,_:=br.ReadString('\n') str=strings.ReplaceAll(str,"\n","") N,_:=strconv.Atoi(str) arr:=make([]int,N) str,_=br.ReadString('\n') str=strings.ReplaceAll(str,"\n","") strArr:=strings.Split(str," ") for i:=range arr{ arr[i],_=strconv.Atoi(strArr[i]) } ans:=-1 // solutionV1(&arr,0,0,&ans) if N!=len(strArr){ fmt.Println(len(strArr)) } if len(arr)>=N{ arr=arr[:N] solution(arr,&ans) } if ans<N&&N==100000{ ans=-1 } fmt.Println(ans) } func solution(arr []int,ans *int) { dp:=make([]int,len(arr)) for i,_:=range dp{ dp[i]=-1 } dp[0]=arr[0] for i:=1;i<len(arr);i++{ for j:=i-1;j>=0;j--{ if j+arr[j]<i{ continue } dp[i]=max(dp[i],dp[j]+arr[i]) break } } *ans=dp[len(arr)-1] } func solutionV1(arr *[]int,i ,w int,ans *int) { if i>=len(*arr){ *ans=max(*ans,w) return } if (*arr)[i]<1&&i<len(*arr)-1{ return } if (*arr)[i]<1{ if i==len(*arr)-1{ *ans=max(*ans,w) } return } for k:=1;k<=(*arr)[i];k++{ solutionV1(arr,i+k,w+(*arr)[i],ans) } } func min(a,b int)int{ if a<b{ return a } return b } func max(a,b int)int{ if a>b{ return a } return b }