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
Daily Recommendation