问题
  • 板块学术版
  • 楼主Nostopathy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/10 09:56
  • 上次更新2024/7/10 11:11:14
查看原帖
问题
1286053
Nostopathy楼主2024/7/10 09:56

样例不过 求条~

描述
给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。

1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1

2.如果无法跳跃(即数组长度为0),也请返回-1

3.数据保证返回的结果不会超过整形范围,即不会超过2^31−1

输入描述:
第一行输入一个正整数 n 表示数组 nums的长度

第二行输入 n 个整数,表示数组 nums 的所有元素的值

输出描述:
输出能获得的最多的积分

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int nums[2024];
int DP[2024];
void DP_(){
	DP[0] = nums[0];
	for(int i = 0; i < n; ++ i){
		for(int j = i + 1; DP[i] && j < n && j < nums[i] + i + 1; ++ j){
			DP[j] = max(DP[i] + DP[j], DP[j]);
		}
	}
}
int main(){
	cin >> n;
	for(int i = 0; i < n; ++ i) cin >> nums[i];
	DP_();
	cout << (DP[n - 1] == 0 ? -1 : DP[n - 1]) << '\n';
}
2024/7/10 09:56
加载中...