搜索>>P2392 kkksc03考前临时抱佛脚

P2392 kkksc03考前临时抱佛脚 链接此处

一句话题意

每个科目有S道习题分别耗时\(a_i\),现在左右脑可以同时做题,求最短耗时\((1<=S<=20)\).

关键

这道题看起来贪心或者背包,但看到数据范围(1<=S<=20),搜索+回溯的复杂度是\(2^n\),可以支持到22,23 ,又因为我们要针对性地去考虑每一道题该让左脑还是右脑去做,我们就用DFS+回溯去秒这道题

int L,R,minval,ans;//L:左脑耗时 R:右脑耗时
int n[5];
int a[5][N];//a[i][j]:表示在第i样作业中第j道题目
void dfs(int x,int now_n)//做了x道题,在第now_n个科目中
{
    if(x>n[now_n])//如果题目做完了
    {
        minval=min(minval,max(L,R));//最少时间等于左右脑耗时最多的半边
        return;
    }
	//左脑
    L+=a[now_n][x];//加上这个题目
    dfs(x+1,now_n);//下一层
    L-=a[now_n][x];//回溯:我没做!
	//右脑
    R+=a[now_n][x];
    dfs(x+1,now_n);
    R-=a[now_n][x];
}

还有要注意:L,R处理空一行,不然混在一起都分辨不出

知识网络

(2026年2月7日15:30:28)
搜索=>DFS+回溯