2013年9月4日

UVa 10898 - Combo Deal

#include <cstdio>
#include <queue>
#include <vector>
#define PB push_back
using namespace std;

struct Combo {
  Combo() {
    for (int i = 0; i < 6; i++) {
      num[i] = 0;
    }
  }
  int num[6], price;
};

int best[1000000];

int main() {
  int N;
  while (scanf("%d", &N) == 1) {
    vector<Combo> combos;
    for (int i = 0; i < N; i++) {
      Combo combo;
      scanf("%d", &combo.price);
      combo.num[i] = 1;
      combos.PB(combo);
    }
    int M;
    scanf("%d", &M);
    while (M--) {
      Combo combo;
      for (int i = 0; i < N; i++) {
        scanf("%d", &combo.num[i]);
      }
      scanf("%d", &combo.price);
      combos.PB(combo);
    }
    int last = 0;
    for (int i = 0; i < N; i++) {
      last = last * 10 + 9;
    }
    for (int i = 1; i <= last; i++) {
      best[i] = 2e9;
    }
    best[0] = 0;
    for (int price = 0; price <= last; price++) {
      if (best[price] == 2e9) {
        continue;
      }
      int num[6] = {};
      for (int temp = price, d = N - 1; temp; temp /= 10, d--) {
        num[d] = temp % 10;
      }
      for (int i = 0; i < combos.size(); i++) {
        int next[6] = {}, index = 0;
        bool push = true;
        for (int j = 0; j < N && push; j++) {
          next[j] = num[j] + combos[i].num[j];
          index = index * 10 + next[j];
          push = (next[j] <= 9);
        }
        if (!push) {
          continue;
        }
        best[index] = min(best[index], best[price] + combos[i].price);
      }
    }
    scanf("%d", &M);
    while (M--) {
      int index = 0;
      for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        index = index * 10 + num;
      }
      printf("%d\n", best[index]);
    }
  }
  return 0;
}

沒有留言:

張貼留言