2013年8月26日

UVa 10980 - Lowest Price in Town

#include <cstdio>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {
  char s[99];
  int C = 1;
  while (gets(s)) {
    double price[201] = {};
    for (int i = 2; i <= 200; i++) {
      price[i] = 2e9;
    }
    int m;
    sscanf(s, "%lf%d", &price[1], &m);
    while (m--) {
      gets(s);
      int num;
      double p;
      sscanf(s, "%d%lf", &num, &p);
      price[num] = min(price[num], p);
    }
    for (int i = 1; i <= 200; i++) {
      for (int j = 0; j < i; j++) {
        price[i] = min(price[i], price[i - j] + price[j]);
      }
    }
    for (int i = 199; i; i--) {
      price[i] = min(price[i], price[i + 1]);
    }
    printf("Case %d:\n", C++);
    gets(s);
    istringstream ss(s);
    int k;
    while (ss >> k) {
      printf("Buy %d for $%.2lf\n", k, price[k]);
    }
  }
  return 0;
}

沒有留言:

張貼留言