题意：n个人， 要完成a个x任务， b个y任务。
求，最短的时间
思路：由于时间较大，用 二分来找时间。
dp[i][j]表示 i个人完成j个x任务， 最多能完成的y任务个数
这个题 不是很好想， 还参考了一下大神的博客
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = +;
int d[][]; int _max(int a, int b)
{
return a>b?a:b;
}
int _min(int a, int b)
{
return a>b?b:a;
}
int main()
{
int t, i, j, k, n, x, y, ca;
int a[maxn], b[maxn];
int low, high, mid, cnt, t1;
scanf("%d", &t);
for(ca = ; ca <= t; ca++)
{
low = ;
high = ;
scanf("%d%d%d", &n, &x, &y);
for(i = ; i <= n; i++)
{
scanf("%d%d", &a[i], &b[i]);
high += x*a[i] + y*b[i];
}
while(high>low)
{
mid = (low+high)/;
memset(d, -, sizeof(d));
d[][] = ;
for(i = ; i <= n; i++)
for(j = ; j <= x; j++)
{
if(d[i-][j]!=-)
{
cnt = _min(mid/a[i], x-j);
for(k = ; k <= cnt; k++)
{
t1 = (mid-k*a[i])/b[i];
if(d[i][j+k]<d[i-][j]+t1)
d[i][j+k] = d[i-][j]+t1;
}
}
}
if(d[n][x]>=y)
high = mid;
else
low = mid+;
}
printf("Case %d: %d\n", ca, high);
}
return ;
}