- 2020-08-02 05:45
*views 4*- DP
- undefined Algorithm exercises
- Java

There's a treasure rack. Yes n layer , The number of treasures in each layer varies , Every treasure has its value , Now ask for it m A treasure , And you need to follow the rules ：

You can only take treasures from both ends of the selected layer at a time

What to take out m The total value of each treasure is the largest of all schemes

input ：

n It's the number of layers ,m It's the number of selections .n<=100,m<=10000

Each row below represents each layer , And the first number is the number of treasures in this layer k, The last one is k The value of a treasure c

Examples ： 2 3 2 3 2 4 1 4 1 5 output ：10

explain ：

5+3+2=10

1<=n,k,c<=100

1<=m<=10000

Input the quantity of treasure enough to take

General idea ：

First ask for each line to be able to take i The maximum value of a treasure, and you have to take it from both ends <=> We take the smallest part from the middle , Then subtract the smallest fraction from the sum of all the treasures in this line

And then take each line i A treasure has been found , And then in the dp Piece together , Find the maximum value

import java.util.Scanner; public class Demo222 { public static void main(String

[] args) { Scanner sc = new Scanner(System.in); // input n Yes , And take m A treasure int n = sc.

nextInt(); int m = sc.nextInt(); //num[i][j] It represents , The first i That's ok , take j Maximum value of treasures int[][] num = new

int[n][]; int index = 0; // Record how many lines of treasure there are int maxSizeRow = n; // Loop a few lines while (n-- > 0)

{ // Enter the treasure of the current line int len = sc.nextInt(); int[] temp = new int[len]; for (int i = 0;

i< len; i++) { temp[i] = sc.nextInt(); } //maxVal[i] It means take i Maximum value of treasures int[] maxVal =

new int[len + 1]; int[] prevSum = new int[len]; // Prefix Sum prevSum[0] = temp[0];

// Attach initial values , The prefix sum of the first number is the first number int sum = temp[0]; for (int i = 1; i < len; i++) {

prevSum[i] = prevSum[i - 1] + temp[i]; sum += temp[i]; } maxVal[len] = sum;

// Take all the things in the current line, which is the sum of these treasures /* * The idea used here is ： * We get the word , You can only take both ends , Get the maximum *

Let's change our thinking , We only take the minimum in the middle , So what's left is the maximum * * */ for (int i = 1; i < len; i++) { // take i A treasure

int minVal = prevSum[i - 1]; for (int j = 0; j < len - i; j++) { // from j Position start int k

= i + j; //k To get the end position （ from j Location i One is to arrive i+j position ） // Find the smallest in the middle Here is the value of the smallest segment minVal = Math.min(

minVal, prevSum[k] - prevSum[j]); } // We have achieved yes i Minimum value of treasure , Then it is to take （ The number of treasures in this layer -i） Treasure of maximum value

maxVal[len - i] = prevSum[len - 1] - minVal; } // Put in our num array ,index It's for word wrap num[

index++] = maxVal; } //dp[i][j] It's us from the beginning to the end i Access j Maximum value of treasures 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++) {

// The maximum value is to take the next floor [j-k] Take a treasure on this floor k A treasure （ here num[i-1] It's because of us num It's from No 0 Line started to join ） dp[i][j] = Math.max(

dp[i - 1][j - k] + num[i - 1][k], dp[i][j]); } } } System.out.println(dp[

maxSizeRow][m]); } }

Technology

- Flow Chart79 blogs
- Python77 blogs
- Java76 blogs
- Vue41 blogs
- MySQL27 blogs
- Linux22 blogs
- javascript20 blogs
- Database18 blogs
- more...

Daily Recommendation

views 9

views 7

views 6

views 5

views 4

©2020 ioDraw All rights reserved

Dormitory information management system JQ set up cookie（3 We'll do it in five minutes ）VUE Arrangement of basic knowledge points Embedded Software Engineer 2019 Summary of school recruitment First order low pass filter - Continuous to discrete python Basic exercises （ One ）Java——char Types and strings Six Star Education ：PHP Programmer's book , Let you quickly become a technical master springboot+vue+shiro Function authority 【Pytorch】BCELoss and BCEWithLogitsLoss Detailed explanation of loss function