[daily question] Porter (DFS / DP)

Title Description
The other day , New students from senior one are coming , He peddles his books as usual , After a lot of talking , The students decided to buy his book , But there are three piles of books on Mr. Chen's desk , Each pile has a thick stack , He should find a way to take down the book in the easiest way and give it to his classmates . But you want to tease teacher Chen , So you design a most tiring way for him . If I tell you that these three piles have i,j,k This book , And the quality of each pile of books from bottom to top , You can only take books from the top of any pile every time , Then please design a plan , Let him try his best to take down all the books .
obviously , Teacher Chen's physical exertion will increase every time he takes the book , Here, the coefficient of physical strength is used to represent , When you take down the first book , Physical strength coefficient is 1, The physical strength coefficient of the second book is 2, By analogy , And the value of each physical exertion is the product of the physical coefficient and the weight of the book .

Input format
The first line has three integers , They are the number of three stacks of books i,j,k.
The second row to the fourth row are the weight of each pile of books from bottom to top .
Output format
Output the total physical exertion of the most tiring way .
sample input
3 2 4
2 3 2
1 5
9 8 7 4
sample output
257
Topic link ： hamal

Ideas 1：（DFS）
   You can search every kind of book retrieval , Record physical exertion in various situations , Taking the maximum

Code ：

import java.util.Scanner;
public class Main {
    
	static int i, j, k;
	static int[] num1,num2,num3;// An array of three stacks of books 
	static int res = 0; // final result 
	public static void main(String[] args) {
    
		Scanner sc = new Scanner(System.in);
		i = sc.nextInt(); j = sc.nextInt() ; k = sc.nextInt();
		num1 = new int[i+1]; num2 = new int[j+1]; num3 = new int[k+1];
		for (int a = 1; a <= i; a++) num1[a] = sc.nextInt();
		for (int a = 1; a <= j; a++) num2[a] = sc.nextInt();
		for (int a = 1; a <= k; a++) num3[a] = sc.nextInt();
		dfs(0, 1);
		System.out.println(res);
	}
	/** * @param temp  Record the physical exertion of taking books in some way  * @param t  Current physical strength coefficient  */
	public static void dfs(int temp, int t) {
    
		if (i + j + k ==0) {
    	// All for 0 Tense means that you have finished taking , Update results 
			res = Math.max(res, temp);
			return;
		}
		if (i > 0) {
    // There is surplus in this heap , Can continue to get this stack 
			temp += t * num1[i--];	// Take the situation 
			dfs(temp, t+1);
			temp -= t * num1[++i];	// If you don't take it, go back 
		}
		if (j > 0) {
    
			temp += t * num2[j--];
			dfs(temp, t+1);
			temp -= t * num2[++j];
		}
		if (k > 0) {
    
			temp += t * num3[k--];
			dfs(temp, t+1);
			temp -= t * num3[++k];
		}
	}
}

Ideas 2：（DP）
   use dp[a][b][c] It means that the number of three stacks of books is a,b,c when , The greatest consumption of physical strength , It's for dp[a-1][b][c] + num1[a] * t ,dp[a][b-1][c] + num2[b] * t and dp[a][b][c-1] + num3[c] * t Of which t Is the current physical strength coefficient

Code ：

import java.util.Scanner;
public class Main {
    
	public static void main(String[] args) {
    
		Scanner sc = new Scanner(System.in);
		int i = sc.nextInt(), j = sc.nextInt(), k = sc.nextInt();
		int sum = i + j + k;	// Total number of books 
		int[] num1 = new int[i+1], num2 = new int[j+1], num3 = new int[k+1];
		for (int l = 1; l <= i; l++) num1[l] = sc.nextInt();// The weight of each book stored in each pile 
		for (int l = 1; l <= j; l++) num2[l] = sc.nextInt();
		for (int l = 1; l <= k; l++) num3[l] = sc.nextInt();
		int[][][] dp = new int[i+1][j+1][k+1];
		for (int a = 0; a <= i; a++) 
			for (int b = 0; b <= j; b++) 
				for (int c = 0; c <= k; c++) {
    
					// The current physical strength coefficient is the total number of books minus a,b,c The value of the add  1
					int t = sum - a - b - c + 1;
					if (a > 0) 
						dp[a][b][c] = dp[a-1][b][c] + num1[a] * t;
					if (b > 0)
						dp[a][b][c] = Math.max(dp[a][b-1][c] + num2[b] * t, dp[a][b][c]);
					if (c > 0)
						dp[a][b][c] = Math.max(dp[a][b][c-1] + num3[c] * t, dp[a][b][c]);
				}
		System.out.println(dp[i][j][k]);
	}
}