洛谷 P2392 kkksc03考前临时抱佛脚 刷题笔记 dfs

P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态

题目分析  

左右脑双核

当我们给左右脑各自分配一道题时 

消耗的时间为两者中耗时较长的一道题

我们尝试把每一道题都分配给左右脑试一试 即可遍历所有答案

关键在于答案怎么取保证耗时最短

if(step>a[x]){//当我们得到一个分配好的方案时

        minv=min(minv,max(l,r));//Min函数内比较的是当前最短耗时 和max函数的结果

     //max函数的结果是当前的实际耗时 即左右脑中耗时较长的一个
        return ;
    }

那么为什么当分配完直接比较左右脑总时长大小即可呢

考虑例子 

1 2 3 9

显然最短时间为

左脑 1 2 3

右脑 9

实际效果和

例子

6 9

是一样的

所以我们可以把一道题直接加给左脑或者右脑 

等所有的题目分配完毕直接比较两个脑子的总时间 取时间较长的作为答案 

完整代码 

#include<bits/stdc++.h>
using namespace std;
int a[5];//记录每科的题目数量
int b[5][21];//记录每道题目的时间
 
const int INF = 0x3f3f3f3f;//1061109567，是10^9级别
 
int l,r,minv,ans;

void dfs(int x,int step){
    if(step>a[x]){
        minv=min(minv,max(l,r));//取所有时间里的最小值
         
        return ;
    }
    l += b[x][step];//将题目分配给左脑  
    dfs(x,step+1);//分配下一道 题目 
    l -= b[x][step];//回溯  
    
    r += b[x][step];
    dfs(x,step+1);
    r -= b[x][step];
    
    
}
int main(){
    for(int i = 1 ;i <= 4;i++){
        cin>>a[i];
    }
    
    for(int i = 1;i <= 4;i++){
        for(int j = 1;j <= a[i];j++){
            cin>>b[i][j];
        }
        l = 0;
        r = 0;
        minv = INF;
        dfs(i,1);
        ans+=minv;
    }
    
    cout<<ans;
    
    
    
    return 0;
}