2013年3月20日

UVa 222 - Budget Travel


#include <stdio.h>

int n;
double target, size, mp, pos[99], price[99], min;

void run(double cost, double loc, double left, double now) {
  if (now == n - 1) {
    left -= (target - loc) / mp;
    if (left >= 0 && cost < min) min = cost;
    return;
  }
  int i;
  for (i = now + 1; i < n; i++)
    if (left * mp >= (pos[i] - loc)) {
      double newLeft = left - (pos[i] - loc) / mp;
      run(cost, pos[i], newLeft, i);
      run(cost + (size - newLeft) * price[i] * 0.01 + 2, pos[i], size, i);
    }
}

int main() {
  int T = 1;
  while (scanf("%lf", &target) && target >= 0) {
    double cost;
    scanf("%lf%lf%lf%d", &size, &mp, &cost, &n);
    int i;
    for (i = 0; i < n; i++)
      scanf("%lf%lf", &pos[i], &price[i]);
    min = 2e9;
    run(cost, 0, size, -1);
    printf("Data Set #%d\nminimum cost = $%.2lf\n", T++, min);
  }
  return 0;
}

沒有留言:

張貼留言