学步园

【题目描述】

n个人，两个项目，各有m个相同部分。每个人完成某个项目的一个部分的时间不同，问最少时间。

【输入格式】

第一行：人数n和部分个数m。

接下来的n行，每行两个数：第i个人完成两个项目的一个部分各需要的时间。

【输出格式】

一行：最快时间。

【样例输入】

3 20

1 1

2 4

1 6

【样例输出】

18

【数据范围】

1<=n,m<=100。

【分析】

二分枚举所用的总的时间，然后用动态规划进行判断是否可以完成。类似唐山一中的同学出的《绿色通道》那道题。但是比那道题目简单。

动归判断：

当前需要判断的时间为mid，用f[i][j]代表前i个人，完成j份第一个项目，第二份项目最多可以完成几份。状态转移方程为f[i][j] = max(f[i - 1][j - k] + (mid - k * w[i][0]) / w[i][1])。最后判断f[n][m]是否大于m即可。

//problem: software company
//by Sephiroth Lee
//date: 10/9/2010
#include <stdio.h>
#include <string.h>
#include <iostream>
#define MAXN 110
using namespace std;
int w[MAXN][2],f[MAXN][MAXN];
int n,m,max_time,l,r,mid;
bool check(int mid) {
  memset(f,-1,sizeof(f));
  f[0][0] = 0;
  for (int i = 1;i <= n;++i)
    for (int j = 0;j <= m;++j) {
      if (f[i - 1][j] < 0) continue;
      for (int k = 0;(j + k <= m) && (mid >= w[i][0] * k);++k)
        if (f[i][j + k] < f[i - 1][j] + (mid - w[i][0] * k) / w[i][1])
          f[i][j + k] = f[i - 1][j] + (mid - w[i][0] * k) / w[i][1];
    }
  return f[n][m] >= m;
}
int main() {
  freopen("software.in","r",stdin);
  freopen("software.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (int i = 1;i <= n;++i) {
    scanf("%d%d",&w[i][0],&w[i][1]);
    if (w[i][0] > max_time)
      max_time = w[i][0];
    if (w[i][1] > max_time)
      max_time = w[i][1];
  }
  r = max_time * m;
  l = 1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n",l);
  return 0;
}