「JoyOI1468」清理垃圾
背景 Background
聚会结束，留下许多垃圾。
Candy：“好多垃圾啊，飘飘乎居士，我们一起处理垃圾吧！”
描述 Description
Candy家里总共有n个垃圾等待处理，每个垃圾对于Candy和飘飘乎居士处理的时间都是不同的，而且每个垃圾只需要一个人处理。当然，Candy和飘飘乎居士可以同时处理不同的垃圾。记两人中耗费最长时间为最后总时间。Candy希望能够尽快的处理完所有的垃圾，因此，他想要知道处理完这些垃圾最少需要耗费多少时间？
输入格式 InputFormat
第一行一个正整数n，表示一共有n个垃圾需要处理
接下来一个2*n的矩阵。
矩阵第一行第i个数表示candy处理第i个垃圾所需消耗的时间
矩阵第二行第i个数表示飘飘乎居士处理第i个垃圾所需消耗的时间
输出格式 OutputFormat
一行，最后耗费的时间
数据范围和注释 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项任务所花的时间。
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，其他的全设为+∞。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,a[1001],b[1001]; int f[1001][4001],ans=0x7fffffff; int main() { scanf("%d",&n); memset(f,127/3,sizeof(f)); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); f[0][0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=4000;j++) if(j>=a[i]) f[i][j]=min(f[i-1][j]+b[i],f[i-1][j-a[i]]); else f[i][j]=f[i-1][j]+b[i]; for(int i=0;i<=4000;i++) ans=min(ans,max(f[n][i],i)); printf("%d",ans); return 0; } |
Subscribe
计数器 9787782
OI 课件=>
OI 课件=>