任务分配（dp）
Description
现有n个任务,要交给A和B完成。每个任务给A或给B完成，所需的时间分别为ai和bi。问他们完成所有的任务至少要多少时间。
Input
第一行一个正整数nn，表示有n个任务。
接下来有n行，每行两个正整数ai，bi。
Output
一个数，他们完成所有的任务至少要的时间。
Samples
Input
3 5 10 6 11 7 12
Output
12
Hint
【输入输出样例解释】
A完成任务1和任务2，时间为11。B完成任务3，时间为12。
或者 A完成任务1和任务3，时间为12。B完成任务2，时间为11。
【限制】
30%的数据满足：1≤n≤20
100%的数据满足：1≤n≤200, 1≤ai,bi≤200
思路：
三维dp比较好推，但是时间空间不允许。
正解是一种比较奇怪的dp状态。
dp[i] [j]的含义为完成前i个任务，A花费的时间为j；
dp[i] [j]的值表示完成前i个任务，B花费的时间。
划分依据为第i个任务由A还是B完成。
代码：
const int maxn=210; int dp[maxn][maxn*maxn]; int a[maxn],b[maxn],n; void solve(){ n=read(); for(int i=1;i<=n;i++){ a[i]=read(),b[i]=read(); } memset(dp,0x3f,sizeof dp); dp[0][0]=0; int sum=0; for(int i=1;i<=n;i++){ sum=sum+a[i]; for(int j=0;j<=sum;j++){ dp[i][j]=dp[i-1][j]+b[i];//b完成第i个任务 if(j>=a[i]) dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]);//a完成第i个任务 } } int res=0x3f3f3f3f; for(int i=0;i<=sum;i++)///可能需要的时间 res=min(res,max(i,dp[n][i]));///注意取的先后顺序 cout<<res<<endl; }
