建立网站加强家园沟通和联系的利弊,亚马逊全球开店官方网站,wordpress后台加统计代码,wordpress 连接插件题目来自蓝桥云
// 这是一个Java程序#xff0c;用于解决最长不下降子序列问题。
// 问题描述#xff1a;给定一个整数序列#xff0c;找到最长的子序列#xff0c;使得这个子序列是不下降的#xff08;即相邻的元素不严格递减#xff09;。
// 程序使用了动态规划的方法…
题目来自蓝桥云
// 这是一个Java程序用于解决最长不下降子序列问题。
// 问题描述给定一个整数序列找到最长的子序列使得这个子序列是不下降的即相邻的元素不严格递减。
// 程序使用了动态规划的方法来解决这个问题。import java.util.*;public class Main {// n表示序列的长度m表示背包的容量static int n, m;// w和t分别表示物品的重量和价值static int[] w new int[256];static int[] t new int[256];// dp数组用于存储动态规划的结果static long[] dp new long[1010];public static void main(String[] args) {Scanner sc new Scanner(System.in);// 读入序列的长度和背包的容量n sc.nextInt();m sc.nextInt();// 读入序列中的每个元素的重量和价值for (int i 1; i n; i) {w[i] sc.nextInt();t[i] sc.nextInt() * 1000; // 将时间单位转换为毫秒}// 使用二分查找法寻找满足条件的最大整数解int l 0, r 25000000;while (l 1 ! r) {int mid l (r - l) / 2;if (check(mid)) {l mid;} else {r mid;}}// 输出满足条件的最大整数解System.out.println(l);}// 检查给定速度下是否能完成任务public static boolean check(int x) {Arrays.fill(dp, -25000000L);dp[0] 0;// 遍历物品更新动态规划表for (int i 1; i n; i)for (int j m; j 0; j--)// 选择放置或不放置物品dp[Math.min(j w[i], m)] Math.max(dp[Math.min(j w[i], m)], dp[j] t[i] - (long) w[i] * x);// 判断是否能完成所有任务return dp[m] 0;}
}
