【tyvj1468】清理垃圾

2014年3月4日1,0960

背景 Background

聚会结束,留下许多垃圾。
Candy:“好多垃圾啊,飘飘乎居士,我们一起处理垃圾吧!”

描述 Description

Candy家里总共有n个垃圾等待处理,每个垃圾对于Candy和飘飘乎居士处理的时间都是不同的,而且每个垃圾只需要一个人处理。当然,Candy和飘飘乎居士可以同时处理不同的垃圾。记两人中耗费最长时间为最后总时间。Candy希望能够尽快的处理完所有的垃圾,因此,他想要知道处理完这些垃圾最少需要耗费多少时间?

输入格式 InputFormat

第一行一个正整数n,表示一共有n个垃圾需要处理
接下来一个2*n的矩阵。
矩阵第一行第i个数表示candy处理第i个垃圾所需消耗的时间
矩阵第二行第i个数表示飘飘乎居士处理第i个垃圾所需消耗的时间

输出格式 OutputFormat

一行,最后耗费的时间

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

Candy完成垃圾3与垃圾4的清理,耗时为5
飘飘乎居士完成垃圾1 2 5的清理,耗时为4,由于Candy耗费的时间较长,所以记Candy耗费时间为最后总时间,所以最后答案为5。
对于30%的数据 0<n<=30
对于100%的数据 0<n<=1000,Candy和飘飘乎居士处理每个垃圾的时间<=10,对任何一个人处理所有垃圾时间总和<=4000

题解
F[i,j]表示:完成前i项任务,若Candy花了j分钟,那么飘飘乎居士最少花F[i,j]分钟。
A[i]表示:Candy完成第i项任务所花的时间。
B[i]表示:飘飘乎居士完成第i项任务所花的时间。

那么有以下DP方程:
F[i,j]=Min{F[i-1,j]+B[i],F[i-1,j-A[i]]}

边界条件是F[0,0]=0,其他的全设为+∞。