当前位置:网站首页>[daily question] Porter (DFS / DP)
[daily question] Porter (DFS / DP)
2022-07-06 09:09:00 【Easenyang】
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]);
}
}
边栏推荐
- 【每日一题】搬运工 (DFS / DP)
- Different data-driven code executes the same test scenario
- Booking of tourism products in Gansu quadrupled: "green horse" became popular, and one room of B & B around Gansu museum was hard to find
- 什么是MySQL?MySql的学习之路是怎样的
- LeetCode:39. Combined sum
- UML diagram memory skills
- [oc]- < getting started with UI> -- common controls - prompt dialog box and wait for the prompt (circle)
- LeetCode:劍指 Offer 42. 連續子數組的最大和
- LeetCode:剑指 Offer 03. 数组中重复的数字
- Pytest's collection use case rules and running specified use cases
猜你喜欢
LeetCode41——First Missing Positive——hashing in place & swap
Nacos 的安装与服务的注册
BMINF的後訓練量化實現
什么是MySQL?MySql的学习之路是怎样的
LeetCode:498. 对角线遍历
BN folding and its quantification
Advanced Computer Network Review(4)——Congestion Control of MPTCP
如何正确截取字符串(例:应用报错信息截取入库操作)
Cesium draw points, lines, and faces
[OC foundation framework] - [set array]
随机推荐
Problems encountered in connecting the database of the project and their solutions
Leetcode: Sword Finger offer 42. Somme maximale des sous - tableaux consécutifs
Revit secondary development Hof method calls transaction
什么是MySQL?MySql的学习之路是怎样的
Compétences en mémoire des graphiques UML
LeetCode:673. Number of longest increasing subsequences
CSP first week of question brushing
Mise en œuvre de la quantification post - formation du bminf
LeetCode:26. 删除有序数组中的重复项
Selenium+pytest automated test framework practice
LeetCode:41. 缺失的第一个正数
【剑指offer】序列化二叉树
LeetCode:124. 二叉树中的最大路径和
一改测试步骤代码就全写 为什么不试试用 Yaml实现数据驱动?
Simclr: comparative learning in NLP
[oc]- < getting started with UI> -- common controls uibutton
【文本生成】论文合集推荐丨 斯坦福研究者引入时间控制方法 长文本生成更流畅
Intel Distiller工具包-量化实现1
What are the common processes of software stress testing? Professional software test reports issued by companies to share
LeetCode:162. Looking for peak