随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,x,y;
int a[55] , b[55] , dp[55][222];
bool check(int mid) {
 memset(dp,-1,sizeof(dp));
 dp[0][0] = 0;
 for(int i=1;i<=n;i++) {
  if(dp[i][x]>=y) return true;
  for(int j=0;j<=x;j++) {
   if(dp[i-1][j] != -1) {
    int tmp = min(mid/a[i] , x - j);
    for(int k=0;k<=tmp;k++) {
     int t = (mid-a[i]*k) / b[i];
     if(dp[i][j+k] < dp[i-1][j] + t)
      dp[i][j+k] = dp[i-1][j] + t;
    }
   }
  }
 }
 if(dp[n][x] >= y) return true;
 return false;
}
int main() {
 int T,cas = 1;
 scanf("%d",&T);
 while(T--) {
  scanf("%d%d%d",&n,&x,&y);
  for(int i=1;i<=n;i++) {
   scanf("%d%d",&a[i],&b[i]);
  }
  int left = 0 ,right = a[1] *x + b[1] * y;
  int ans = -1;
  while(left <= right) {
   int mid = (left + right) >> 1;
   if(check(mid)) {
    ans = mid;
    right = mid - 1;
   }
   else left = mid + 1;
  }
  printf("Case %d: %d\n",cas++,ans);
 }
 return 0;
}