最大和
本文最后更新于 202 天前,其中的信息可能已经有所发展或是发生改变。

最大和

小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 �n 个方格, 依次编号 1 至 �n, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。

小蓝开始时站在方格 1 上并获得了方格 1 上宝物的分值, 他要经过若干步 到达方格 �n

当小蓝站在方格 �p 上时, 他可以选择跳到 p+1 到 p+D(np) 这些方格 中的一个, 其中 �(1)=1,�(�)(�>1)D(1)=1,D(x)(x>1) 定义为 �x 的最小质因数。

给定每个方格中宝物的分值, 请问小蓝能获得的最大总分值是多少。**前缀和

 import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n = scan.nextInt(); //方格数
int[] temp = new int[n+1];//各个方格的分值
int[] v = new int[n+1]; //走到各个方格的最大值
for(int i = 1;i<n+1;i++){
temp[i]=scan.nextInt();
}
for(int i = 2;i<n+1;i++){
v[i]=Integer.MIN_VALUE;
}
v[1]=temp[1];//默认站在方格1的值
//遍历所有到n的路径
for(int i=1;i<=n;i++){
int next = findMinPf(n-i);//当前方格D的值(最小质因数)
//遍历当前方格所有可以走的路径
for(int j=1;j<=next;j++){
v[j+i]=Math.max(v[j+i],v[i]+temp[j+i]);//存下遍历中的最大值
}
}
System.out.print(v[n]);//输出走到方格n的最大值
}
//找最小质因数函数
private static int findMinPf(int index){
if(index==1)return 1; //D(1)=1
//从2开始遍历到index之间的所有值,找到最小的质因数
for(int i=2;i<index;i++){
if(index%i==0)return i;//如果能被i整除,i就是最小质因数,返回i
}
return index;//找不到就说明index是最小质因数,返回index
}
}

我的感受:

这题确实很难,但是难不倒我!

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇