tyvj1468 清理垃圾

背景

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

描述

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

输入格式

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

输出格式

一行,最后耗费的时间

测试样例1

输入


2 4 1 4 5 
2 1 3 4 1

输出

5

备注

Candy完成垃圾3与垃圾4的清理,耗时为5
飘飘乎居士完成垃圾1 2 5的清理,耗时为4,由于Candy耗费的时间较长,所以记Candy耗费时间为最后总时间,所以最后答案为5。
对于30%的数据 0<n<=30
对于100%的数据 0<n<=1000,Candy和飘飘乎居士处理每个垃圾的时间<=10,对任何一个人处理所有垃圾时间总和<=4000
 
/*
只有一个“前i个垃圾”不满足最优子结构,加一位状态表示candy清理的数量
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define fd(i,l,r) for(int i = r;i >= l;i--)
using namespace std;
ll read(){
ll x=,f=;
char ch=getchar();
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
int n,a[],b[],dp[][],ans = ;
bool vis[];
int main(){
n = read();
fo(i,,n) a[i] = read();
fo(i,,n) b[i] = read();
memset(dp,/,sizeof(dp));
dp[][] = ;
fo(i,,n){
fo(j,,){
if(j >= a[i]) dp[i][j] = min(dp[i][j],dp[i-][j-a[i]]);
dp[i][j] = min(dp[i][j],dp[i-][j] + b[i]);
if(i == n) ans = min(max(dp[i][j],j),ans);
}
}
cout<<ans;
return ;
}
上一篇:Delphi TNativeXML Node节点乱码的一种解决方法


下一篇:react初探(一)之JSX、状态(state)管理、条件渲染、事件处理