题目链接: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 }