邢台移动网站建设报价,福田服务商app软件安装,2023必考十大时政热点,建设局平台小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 nn 个方格, 依次编号 1 至 nn, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。 小蓝开始… 小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 nn 个方格, 依次编号 1 至 nn, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。 小蓝开始时站在方格 1 上并获得了方格 1 上宝物的分值, 他要经过若干步 到达方格 nn。 当小蓝站在方格 pp 上时, 他可以选择跳到 p1p1 到 pD(n-p)pD(n−p) 这些方格 中的一个, 其中 D(1)1, D(x)(x1)D(1)1,D(x)(x1) 定义为 xx 的最小质因数。 给定每个方格中宝物的分值, 请问小蓝能获得的最大总分值是多少。 输入格式 输入的第一行包含一个正整数 nn 。 第二行包含 nn 个整数, 依次表示每个方格中宝物的分值。 输出格式 输出一行包含一个整数, 表示答案。 5 1 -2 -1 3 5 输出 8 本题一开始采用的动态规划dp[i]表示在i位置的获得的最大价值。这是本人一开始的动态规划但是时间超时只能换种方法。 for(int i2;in;i){dp[i]dp[i-1]nums[i];for(int j1;ji;j){int xn-j;int m m(x);if(mji)dp[i]Math.max(dp[i],dp[j]nums[i]);}}
真题代码 public static void main(String[] args){Scanner scannernew Scanner(System.in);int nscanner.nextInt();int nums[]new int[n1];for(int i1;in;i){nums[i]scanner.nextInt();}int[] dpnew int[nums.length];Arrays.fill(dp,Integer.MIN_VALUE);dp[1]nums[1];for(int i1;in;i){int mm(n-i);for(int ji1;jim;j){dp[j]Math.max(dp[j],dp[i]nums[j] );}}System.out.println(dp[n]);}public static int m(int x){for(int i2;iMath.sqrt(x);i){if(x%i0)return i;}return x;}话说大诗人李白, 一生好饮。幸好他从不开车。 一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱: 无事街上走提显去打酒。 逢店加一倍, 遇花喝一斗。 这一路上, 他一共遇到店 NN 次, 遇到花 MM 次。已知最后一次遇到的是花, 他正好把酒喝光了。 请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能? 注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。 输入格式 第一行包含两个整数 NN 和 MM. 输出格式 输出一个整数表示答案。由于答案可能很大输出模 1000000007 的结果. 样例输入 5 10样例输出 14 摘自蓝桥杯题解代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
//dp[n][m][k]表示遇见n店m花还剩k酒。
//因为题目要求最后一次必须是花因此倒数第二次肯定剩余1数量的酒。
//所以答案ans dp[n][m-1][1]。
//当剩余偶数酒的时候有可能你上次遇见花也遇见店。
//当剩余奇数酒的时候你上次必遇见店。
public class Main {public static final int mod (int)1e97;public static void main(String[] args) {Scanner scan new Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][][] dp new int[n1][m1][m5];dp[0][0][2]1;dp[0][1][1]1;dp[0][2][0]1;for(int i1;in;i){for(int j0;jm;j){for(int k0;km;k){if(i0k0k%20)dp[i][j][k]dp[i-1][j][k/2];if(j0)dp[i][j][k]dp[i][j-1][k1];dp[i][j][k]%mod;}}}System.out.println(dp[n][m][0]%mod);scan.close();}
}
