本文主要是介绍洛谷P2392题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。
题目描述
这次期末考试，kkksc03 需要考 4 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1，B1,B2,…,Bs2，C1,C2,…,Cs3，D1,D2,…,Ds4）。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 2 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入格式
本题包含 5 行数据：第 11 行，为四个正整数 s1,s2,s3,s4。
第 2 行，为A1,A2,…,As1 共 s1 个数，表示第一科习题集每道题目所消耗的时间。
第 3 行，为 B1,B2,…,Bs2 共 s2 个数。
第 44 行，为 C1,C2,…,Cs3 共 s3 个数。
第 55 行，为 D1,D2,…,Ds4 共 s4 个数，意思均同上。
输出格式
输出一行,为复习完毕最短时间。
输入输出样例
输入 #1
1 2 1 3 5 4 3 6 2 4 3
输出 #1
20
说明/提示
1≤s1,s2,s3,s4≤20。
1≤A1,A2,…,As1,B1,B2,…,Bs2,C1,C2,…,Cs3,D1,D2,…,Ds4≤60。
思路
这道题应该用dp，对于一道题只有两个状态，一是加到左脑，二是加到右脑，所以是01背包。
这里还可以用另一个思想，将一边的脑子加到最接近一半则另一边脑子时间就是正解。
AC Code
#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,k,sum,t,homework[21],dp[2501];
int main(){for(i=1;i<=4;i++)cin>>a[i];for(i=1;i<=4;i++){sum=0; for(j=1;j<=a[i];j++){cin>>homework[j];sum+=homework[j];}for(j=1;j<=a[i];j++)for(k=sum/2;k>=homework[j];k--)dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);t+=sum-dp[sum/2];for(j=1;j<=sum/2;j++)dp[j]=0;}cout<<t;return 0;
}由于我不知道怎么在博客中呈现下标字，给您的阅读带来的不便，敬请谅解。
这篇关于洛谷P2392题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
