当前位置:网站首页>【每日一题】搬运工 (DFS / DP)
【每日一题】搬运工 (DFS / DP)
2022-07-06 08:59:00 【Easenyang】
题目描述
前些天,高一的新同学来了,他便像往常一样兜售他的书,经过一番口舌,同学们决定买他的书,但是陈老师桌上的书有三堆,每一堆都有厚厚的一叠,他要想个办法用最轻松的方式把书拿下来给同学们。但是你想逗一下陈老师,于是你设计一个最累的方式给他。若告诉你这三堆分别有i,j,k 本书,以及每堆从下到上书的质量,每次取书只能从任一堆的最上面取,那么请你设计一个方案,让他花最大的力气取下所有的书。
显然,每次取书陈老师的体力消耗都会加大,这里用体力系数代表,取下第一本书时,体力系数为 1,第二本书时体力系数为2,依次类推,而每次体力消耗值则为体力系数与书的重量之积。输入格式
第一行有三个整数,分别为三堆书的数量 i,j,k。
第二行至第四行分别为每堆由下至上的书本重量。
输出格式
输出最累方式的体力消耗总值。
输入样例
3 2 4
2 3 2
1 5
9 8 7 4
输出样例
257
题目链接:搬运工
思路1:(DFS)
可以去搜索每种取书的情况,记录各种情况的体力消耗,取最大值
代码:
import java.util.Scanner;
public class Main {
static int i, j, k;
static int[] num1,num2,num3;//存放三堆书的数组
static int res = 0; //最终结果
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 记录某种方式取书的体力消耗 * @param t 当前体力系数 */
public static void dfs(int temp, int t) {
if (i + j + k ==0) {
//都为0时表示取完了,更新结果
res = Math.max(res, temp);
return;
}
if (i > 0) {
//该堆有剩余,才能继续取本堆的
temp += t * num1[i--]; //取的情况
dfs(temp, t+1);
temp -= t * num1[++i]; //不取则回溯
}
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];
}
}
}
思路2:(DP)
用dp[a][b][c]表示取三堆书的数目分别为a,b,c时,体力的最大消耗,它为dp[a-1][b][c] + num1[a] * t ,dp[a][b-1][c] + num2[b] * t
和 dp[a][b][c-1] + num3[c] * t
的最大值其中 t 为当前体力系数
代码:
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; //书的总数
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();//存放每堆数的每本书重量
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++) {
//当前体力系数为书的总数减去a,b,c的值加 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]);
}
}
边栏推荐
- [OC]-<UI入门>--常用控件-提示对话框 And 等待提示器(圈)
- Digital people anchor 618 sign language with goods, convenient for 27.8 million people with hearing impairment
- How to effectively conduct automated testing?
- Pytest之收集用例规则与运行指定用例
- Niuke winter vacation training 6 maze 2
- LeetCode:387. 字符串中的第一个唯一字符
- [embedded] print log using JLINK RTT
- Marathon envs project environment configuration (strengthen learning and imitate reference actions)
- [OC foundation framework] - string and date and time >
- Advanced Computer Network Review(4)——Congestion Control of MPTCP
猜你喜欢
Excellent software testers have these abilities
Advanced Computer Network Review(4)——Congestion Control of MPTCP
CUDA实现focal_loss
Pytest参数化你不知道的一些使用技巧 /你不知道的pytest
多元聚类分析
Mongodb installation and basic operation
BMINF的後訓練量化實現
Pytest之收集用例规则与运行指定用例
IJCAI2022论文合集(持续更新中)
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
随机推荐
SAP ui5 date type sap ui. model. type. Analysis of the parsing format of date
TDengine 社区问题双周精选 | 第三期
Using label template to solve the problem of malicious input by users
Selenium+Pytest自动化测试框架实战(下)
Intel distiller Toolkit - Quantitative implementation 3
Digital people anchor 618 sign language with goods, convenient for 27.8 million people with hearing impairment
[Hacker News Weekly] data visualization artifact; Top 10 Web hacker technologies; Postman supports grpc
BMINF的後訓練量化實現
可变长参数
LeetCode:387. 字符串中的第一个唯一字符
BMINF的后训练量化实现
BN folding and its quantification
[OC foundation framework] - string and date and time >
什么是MySQL?MySql的学习之路是怎样的
【嵌入式】使用JLINK RTT打印log
What are the common processes of software stress testing? Professional software test reports issued by companies to share
Super efficient! The secret of swagger Yapi
LeetCode:214. Shortest palindrome string
LeetCode:124. Maximum path sum in binary tree
LeetCode:236. The nearest common ancestor of binary tree