【算法分析】 枚举每道题交给哪边的脑子解决，找到两边时间较大值的最小值。 【参考代码】 【时间复杂度】 O(2n)O(2^n)O(2n) nnn 为题目数量 【预计得分】 100pts100pts100pts

背包的容量是总时间的一半，因为左右两个大脑消耗的时间最好各是总时间的一半。

时间复杂度：O(n∗sum(a))O(n * sum(a))O(n∗sum(a))

#include <iostream> using namespace std; const int INF = 2e9; int l, r, minn, ans; //左脑解题花费时间、右脑解题花费的时间，单科最小花费时间，四科花费的总时间 int s[5]; //s[i]表示第i个科目的题目数量 int a[30][5]; //a[j][i] 表示第i个科目的第j个题目解出花费的时间 //搜索所有可能方案，并维护一个最短时间 void dfs(int x, int y) { if (x > s[y]) { //终止条件 minn = min(minn, max(l, r)); return; } l += a[x][y]; //左脑解第x题 dfs(x + 1, y); l -= a[x][y]; //搜索回溯 r += a[x][y]; //右脑解第x题 dfs(x + 1, y); r -= a[x][y];//搜索回溯 } int main() { cin >> s[1] >> s[2] >> s[3] >> s[4]; for (int i = 1; i <= 4; i++) { l = r = 0; //初始化为 0 minn = INF; for (int j = 1; j <= s[i]; j++) cin >> a[j][i]; dfs(1, i); //i科目的第一道题开始搜索 ans += minn; } cout << ans; return 0; }

#include<bits/stdc++.h> using namespace std; int minn=1000000000; int s[5]; int a[30][5]; int l,r,ans; void dfs(int x,int y,int l,int r){ if(x>s[y]){ minn=min(minn,max(l,r)); return ; } dfs(x+1,y,l+a[x][y],r); dfs(x+1,y,l,r+a[x][y]); } int main(){ cin>>s[1]>>s[2]>>s[3]>>s[4]; for(int i=1;i<=4;i++){ minn=1000000000; l=r=0; for(int j=1;j<=s[i];j++){ cin>>a[j][i]; } dfs(1,i,0,0); ans+=minn; } cout<<ans; return 0; }