- 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 Chart77 blogs
- Java38 blogs
- Python32 blogs
- MySQL16 blogs
- Linux16 blogs
- Android15 blogs
- Administration13 blogs
- Database12 blogs
- more...

Daily Recommendation

©2020 ioDraw All rights reserved

Interview questions ： Handwritten list （ Include reverse linked list ）C Notes on language learning —— Pointer ： Pointer and one dimensional array error: (-215:Assertion failed) Solution layui.table Examples of dynamically getting header and list data python Simple record of network programming After the outbreak Which programming has a bright future Java Summary of basic learning （162）—— How to ensure thread safety ?vue el-input Do not enter special characters Only numbers can be entered Regular verification MYSQL database DML Common commands python in list and str Mutual conversion