欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【DFS】搬书

程序员文章站 2024-03-18 23:08:10
...

描述  

  陈老师桌上的书有三堆,每一堆都有厚厚的一叠,你想逗一下陈老师,于是你设计一个最累的方式给他,让他把书拿下来给同学们。若告诉你这三堆分别有i,j,k本书,以及每堆从下到上书的质量,每次取书只能从任一堆的最上面取,显然,每次取书陈老师的体力消耗都会加大,这里用体力系数代表,取下第一本书时,体力系数为1,第二本书时体力系数为2,依次类推,而每次体力消耗值则为体力系数与书的重量之积。书最多有100本。

输入

  第一行3个整数,分别为三堆书的数量i,j,k;第二行至第四行分别为每堆由下至上的书本重量。

输出

  一行,输出最累方式的体力消耗总值

输入样例1

3 2 4
2 3 2 
1 5 
9 8 7 4 

输出样例1

 

257

 

解题思路

  刚开始想的是贪心,每次取三堆中最小的,但是后面被卡住了,发现不行,然后就用熟悉的记忆化搜索(不想用DP,好吧,是还没学),

题解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n1,n2,n3;
 4 int a1[101];
 5 int a2[101];
 6 int a3[101];
 7 int dp[101][101][101];
 8 int dfs(int x,int y,int z)
 9 {
10     int qwe=x+y+z;//体力 
11     if(x<0||y<0||z<0)return 0;//负数取不了啊 
12     if(dp[x][y][z])return dp[x][y][z];//记忆化搜索,剪枝 
13     return dp[x][y][z]=max(dfs(x-1,y,z)+a1[x]*qwe,max(dfs(x,y-1,z)+a2[y]*qwe,dfs(x,y,z-1)+a3[z]*qwe));
14 }//类似于状态转移方程 
15 int main()
16 {
17     cin>>n1>>n2>>n3;
18     for(int i=n1;i>=1;i--)//初始化,倒着存方便 
19     {
20         cin>>a1[i];
21     }
22     for(int i=n2;i>=1;i--)
23     {
24         cin>>a2[i];
25     }
26     for(int i=n3;i>=1;i--)
27     {
28         cin>>a3[i];
29     }
30     dp[1][0][0]=a1[1];//初始化取每一堆的第一本 
31     dp[0][1][0]=a2[1];
32     dp[0][0][1]=a3[1];
33     cout<<dfs(n1,n2,n3);
34     return 0;
35 }

借鉴专用区(大家都懂)

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n1,n2,n3;
 4 int a1[101];
 5 int a2[101];
 6 int a3[101];
 7 int dp[101][101][101];
 8 int dfs(int x,int y,int z)
 9 {
10     int qwe=x+y+z;
11     if(x<0||y<0||z<0)return 0;
12     if(dp[x][y][z])return dp[x][y][z];
13     return dp[x][y][z]=max(dfs(x-1,y,z)+a1[x]*qwe,max(dfs(x,y-1,z)+a2[y]*qwe,dfs(x,y,z-1)+a3[z]*qwe));
14 }
15 int main()
16 {
17     cin>>n1>>n2>>n3;
18     for(int i=n1;i>=1;i--)
19     {
20         cin>>a1[i];
21     }
22     for(int i=n2;i>=1;i--)
23     {
24         cin>>a2[i];
25     }
26     for(int i=n3;i>=1;i--)
27     {
28         cin>>a3[i];
29     }
30     dp[1][0][0]=a1[1];
31     dp[0][1][0]=a2[1];
32     dp[0][0][1]=a3[1];
33     cout<<dfs(n1,n2,n3);
34     return 0;
35 }