洛谷P2392 kkksc03考前临时抱佛脚

题目链接：https://www.luogu.com.cn/problem/P2392

两种思路：

1、常规搜索

2.、dp0/1背包问题

这里本人只提供第一种思路，因为第二种思路我也不会（怎么就成了0/1背包）？

第一种思路具体内容：

这里知道我们在题目中有左右两个脑子，那就本题而言

我们在做某个学科的题目时，无非就是利用两个脑子去解决问题从而获得最短时间，那就好啦

左脑运算时间之后和右脑运算之后取一个最小值

参考代码及注意事项如下：

 1 #pragma GCC optimize(2)//手动开启o2优化，如果主办方没说可以用最好别用 
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int s[5];//4门学科 
 5 int a[5][30];//每门学科题集每道题目所消耗的时间。 
 6 int l;//左大脑 
 7 int r;//右大脑子 
 8 int result;//最后的结果 
 9 int minn;//每门学科所要消耗的最少时间 
10 void dfs(int i,int j)
11 {
12     if(j>s[i])
13     {
14         minn=min(minn,max(l,r));
15         return ;
16     }
17     //左大脑进行运算 
18     l+=a[i][j];
19     dfs(i,j+1);
20     l-=a[i][j];//进行回溯 
21     //右大脑进行运算
22     r+=a[i][j];
23     dfs(i,j+1);
24     r-=a[i][j]; //进行回溯 
25     
26 }
27 int main()
28 {
29     ios::sync_with_stdio(false);//快速输入流 
30     for(int i=1;i<=4;i++)
31     cin>>s[i];
32     for(register int i=1;i<=4;i++)//优化for循环 
33     {
34         for(register int j=1;j<=s[i];j++)
35         {
36             cin>>a[i][j];
37         }
38      } 
39      for(int i=1;i<=4;i++)
40      {
41          l=0;
42          r=0;
43          minn=INT_MAX;//哨兵作用，最小值要先设为无穷大
44         dfs(i,1);
45         result+=minn; //对于每门学科的最少时间进行一个累加以输出最后的总时间即result； 
46      }
47      cout<<result;
48     return 0;
49  }

洛谷P2392 kkksc03考前临时抱佛脚

推荐阅读