Morris' Blog

2013-07-07 21:23:07Morris

[UVA][dp] 10898 - Combo Deal

留言 0 收藏 0 推薦 0

D: Combo Deal

A fast food store offers a series of ``combo meal deals" in addition to individually priced items. For example, the menu at the store may look like this:


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

Buying a combo is cheaper than buying its items individually.

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

The input contains several test cases, each of them with a menu and several orders.

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.
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

For each order of each case, output the minimum payment in cents on its own line.

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

套餐組合一定是便宜的，因此使用動態規劃找最佳解。
但因為不會多買跟少買，又因為有最多六個，每個數量不超過 <= 9。
因此可以壓縮成十進制數 <= 999999。
原本想說進行陣列標記，但有點麻煩就使用了 map<int, int> 當作陣列。

#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int A[10];
int B[10][10], cB[10];
int I, C;
map<int, int> dp;
int dfs(int state) {
    if(state == 0) return 0;
    if(dp.find(state) != dp.end())
        return dp[state];
    int &val = dp[state];
    val = 0xfffffff;
    int v[6] = {}, i, j, xx;
    for(i = I-1; i >= 0; i--)
        v[i] = state%10, state /= 10;
    for(i = 0; i < C; i++) {
        for(j = 0; j < I; j++)
            if(v[j] < B[i][j])
                break;
        if(j != I) continue;
        xx = 0;
        for(j = 0; j < I; j++) {
            v[j] -= B[i][j];
            xx = xx*10 + v[j];
        }
        val = min(val, dfs(xx)+cB[i]);
        for(j = 0; j < I; j++)
            v[j] += B[i][j];
    }
    for(i = 0; i < I; i++) {
        if(v[i] == 0)   continue;
        v[i]--;
        xx = 0;
        for(j = 0; j < I; j++)
            xx = xx*10 + v[j];
        val = min(val, dfs(xx)+A[i]);
        v[i]++;
    }
    return val;
}
int main() {
    int i, j;
    while(scanf("%d", &I) == 1) {
        for(i = 0; i < I; i++)
            scanf("%d", &A[i]);
        scanf("%d", &C);
        for(i = 0; i < C; i++) {
            for(j = 0; j < I; j++)
                scanf("%d", &B[i][j]);
            scanf("%d", &cB[i]);
        }
        int q, x;
        scanf("%d", &q);
        dp.clear();
        while(q--) {
            int xx = 0;
            for(i = 0; i < I; i++) {
                scanf("%d", &x);
                xx = xx*10 + x;
            }
            printf("%d\n", dfs(xx));
        }
    }
    return 0;
}

上一篇：[UVA][formula] 10843 - Anne's game

下一篇：[UVA][模擬] 11242 - Tour de France