有个藏宝架有n层,每层的宝物数量不一,每个宝物都有其价值,现在要求拿出m个宝物,并且需要遵守规则:
每次只能拿选定层的两端的宝物
要拿出的m个宝物的总价值是各种方案里最大的
输入:
n是层数,m是挑选的次数。n<=100,m<=10000
下面每行代表每层,且第一个数是这层宝物的数量k,后面的则是k个宝物的价值c
样例: 2 3 2 3 2 4 1 4 1 5 输出:10
说明:
5+3+2=10
1<=n,k,c<=100
1<=m<=10000
输入保证宝物的数量够拿取的数量

大概思路:
先求每一行能拿i个宝物的最大值而且还要从两端开始拿 <=> 我们从中间取最小的一部分,然后用这一行所有宝物的和减去最小的这一小部分
然后每行的拿i个宝物的求出来了,然后在dp拼凑,求出最大的价值
import java.util.Scanner; public class Demo222 { public static void main(String
[] args) { Scanner sc = new Scanner(System.in); //输入n行的,并且取m个宝物 int n = sc.
nextInt(); int m = sc.nextInt(); //num[i][j]代表的是,第i行,取j个宝物的最大值 int[][] num = new
int[n][]; int index = 0; //记录一下有几行宝物 int maxSizeRow = n; //循环几行 while (n-- > 0)
{ //输入当前行的宝物 int len = sc.nextInt(); int[] temp = new int[len]; for (int i = 0;
i< len; i++) { temp[i] = sc.nextInt(); } //maxVal[i]表示取i个宝物的最大值 int[] maxVal =
new int[len + 1]; int[] prevSum = new int[len]; //求前缀和 prevSum[0] = temp[0];
//附上初始值,第一个数的前缀和就是第一个数 int sum = temp[0]; for (int i = 1; i < len; i++) {
prevSum[i] = prevSum[i - 1] + temp[i]; sum += temp[i]; } maxVal[len] = sum;
//把当前行所有的都拿了就是这些宝物的和 /* * 这里用的思路为: * 我们取得话,只能拿两端得,要能拿到得最大值 *
我们转换一下思路,我们只拿中间得最小值,那么剩下得就是最大值 * * */ for (int i = 1; i < len; i++) { //取i个宝物
int minVal = prevSum[i - 1]; for (int j = 0; j < len - i; j++) { //从j位置开始取 int k
= i + j; //k为取得结束位置(从j位置取i个就是到i+j位置) //找到中间最小得 这里就是最小的那一段得值 minVal = Math.min(
minVal, prevSum[k] - prevSum[j]); } //我们取得是i个宝物得最小值,那么就是取(这一层的宝物数量-i)个最大值的宝物
maxVal[len - i] = prevSum[len - 1] - minVal; } //放入我们的num数组,index是为了自动换行 num[
index++] = maxVal; } //dp[i][j]就是我们从头到i行取j个宝物的最大值 int[][] dp = new int[
maxSizeRow+ 1][m + 1]; for (int i = 1; i <= maxSizeRow; i++) { for (int j = 0; j
<= m; j++) { for (int k = 0; k < num[i - 1].length && j - k >= 0; k++) {
//最大值就是上一层拿[j-k]个宝物这一层拿k个宝物(这里num[i-1]是因为我们的num是从第0行开始加入的) dp[i][j] = Math.max(
dp[i - 1][j - k] + num[i - 1][k], dp[i][j]); } } } System.out.println(dp[
maxSizeRow][m]); } }

技术
©2020 ioDraw All rights reserved
在上海做什么赚钱快?这10个你可以试一试!PHP 先返回结果到前端,PHP代码继续执行后续的任务centos7部署springboot jar包 疫情过后 学哪个编程有前景安卓开发—根据顾客预算显示食物信息苹果iPhone 12全系售价泄露:官方最高售价近1万元log4j打印异常堆栈信息的方法PTA快速排序日经:索尼和铠侠正积极申请华为供货许可一个学生关于鸿蒙系统的一些看法