D: Combo Deal

Hamburger 							 $3.49 


Fries 								 $0.99 


Pop 								 $1.09 


Ice Cream 							 $2.19 


Value Meal (1 Hamburger, 1 Fries, 1 Pop) 			 $4.79 


Lovers-Only (2 Hamburgers, 2 Fries, 2 Pops, 1 Ice Cream)	 $9.99 

A parent of many kids (or a coach of many students) face this recurring problem: I need to get, say, 9 hamburgers, 6 fries, and 8 pops. How do I fit this into the menu, using the combo deals optimally, so as to pay as little as possible? Note that I am a conservativist, so I don‘t buy more food than I need.

Input 

1. Menu: Individual items, then combos.

   (a)

   Individual items: number of items , then their prices (at most $10 each).

   (b)

   Combos: number of combos (at most 8), then for each combo, its composition as an -tuple of quantities and its price.

   Example: the sample input below encodes the menu above.

2. Orders: number of orders (at most 10), then for each order, an -tuple of the wanted quantities. Each element in the tuples is at most 9.

All prices are integers in cents.

Output 

Sample Input 

4 349 99 109 219
2
1 1 1 0 479
2 2 2 1 999
2
9 6 8 0
9 6 8 5

Sample Output 

4139
4700

#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;
}

UVa 10898 Combo Deal DP,布布扣,bubuko.com

UVa 10898 Combo Deal DP

原文：http://blog.csdn.net/china_zoujinyong/article/details/20466925