【洛谷】P2392 kkksc03考前临时抱佛脚

本题最重要的思路是：将题目转化为 01 背包模型。 

注意点：

（1）要求最短时间，则需让左右脑花费的时间最接近，极限状态下是左脑时间和右脑时间相等，且等于 m = sum / 2（其中sum是一道一道做完一科所有题目的总时间）。

（2）从（1）可知，我们要将某科的若干道题目相加，使其总时间最接近 m，此时做完这一科的时间是最短时间。

（3）这道题中，时间既是体积又是价值。

（4）最终返回的时间应该是左右脑时间中的较大值，可以假设左脑时间一直小于等于右脑，也就是左脑时间 ≤ m，故左脑是容积为 m 的01背包。

#include<iostream>
using namespace std;

int t[25];

int f(int n)
{
	int sum = 0;
	// sum 表示一道一道做完所有题目的总时间。 
	// 左右脑所用的时间越接近，最终花费时间就越短， 
	// 故只需求最接近 m=sum/2 的情况下，花费时间的最大值。 
	// 下面假设左脑花费时间始终 ≤m 。 
	int dp[1210] = {0};
	
	for(int i=0;i<n;++i)
	{
		scanf("%d", &t[i]);
		sum += t[i];
	}
	
	if(n == 1) return sum;
	// 只有一道题目则不需要计算直接返回 
	
	int m = sum/2;
	
	// 体积为 m=sum/2 的 01 背包模型 
	for(int i=0;i<n;++i)
	{
		for(int j=m;j>=t[i];--j)
		{
			dp[j] = max(dp[j], dp[j-t[i]] + t[i]);
		}
	}
	
	return sum - dp[m];
	// 上式表示右脑花费时间，
	// 因为前面假设了右脑花费时间始终比左脑多。 
	// 最终结果是取左右脑中较多的时间 
}

int main()
{
	int s1,s2,s3,s4;
	scanf("%d%d%d%d", &s1, &s2, &s3, &s4);
	
	int ans = f(s1) + f(s2) + f(s3) + f(s4);
	// f(i) 表示有 i 道题目时，花费的最短时间 
	
	cout<<ans;
	return 0;
}