Торговые скидки
http://acm.pku.edu.cn/JudgeOnline/problem?id=1170

http://acm.pku.edu.cn/JudgeOnline/images/1170_1.jpg

   В магазине каждый товар имеет цену. Например, цена одного цветка равна 2 ICU (ICU - Informatics Currency Units), а цена одной вазы равна 5 ICU. Чтобы привлечь больше покупателей, магазин ввел скидки.

   Скидка заключается в том, чтобы продавать набор одинаковых или разных товаров по пониженной цене. Примеры: три цветка за 5 ICU вместо 6, или две вазы вместе с одним цветком за 10 ICU вместо 12.

   Напишите программу, вычисляющую наименьшую цену, которую покупатель должен заплатить за заданные покупки. Оптимальное решение должно быть получено посредством скидок. Набор товаров, который требуется купить, нельзя дополнять ничем, даже если бы это снизило общую стоимость набора. Для описанных выше цен и скидок наименьшая цена за три цветка и две вазы равна 14 ICU: две вазы и один цветок продаются по сниженной цене за 10 ICU, и два цветка - по обычной цене за 4 ICU.

   Входные данные

   В первой строке входных данных задано количество b различных видов товара в корзине (0 <= b <= 5). Каждая из следующих b строк содержит значения c, k и p. Значение c - уникальный код товара (1 <= c <= 999). Значение k задает, сколько единиц товара находится в корзине (1 <= k <= 5). Значение p задает обычную (без скидок) цену единицы товара (1 <= p <= 999). Обратите внимание, что общее количество товаров в корзине не может быть более 5*5 = 25 единиц. Далее следует количество s возможных скидок (0 <= s <= 99). Каждая из последующих s строк описывает одну скидку, определяя набор товаров и общую стоимость набора. Первое число n в такой строке определяет количество различных видов товаров в наборе (1 <= n <= 5). Следующие n пар чисел (c, k) указывают, что k единиц товара с кодом c включены в набор для скидки (1 <= k <= 5, 1 <= c <= 999). Последнее число в строке p определяет уцененную стоимость набора (1 <= p <= 9999). Стоимость набора меньше суммарной стоимости отдельных единиц товаров в наборе.

   Выходные данные

   Выведите единственную строку с наименьшей возможной суммарной стоимостью покупок

   Пример входных данных

2
7 3 2
8 2 5
2
1 7 3 5
2 7 1 8 2 10

   Пример выходных данных

14

   Анализ условия и идея решения

   Пример решения на С++

Код:
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 5;

int b, s;
int mark[1000];
int num[maxn], price[maxn];
int reduce[100][maxn];
int reduce_price[100];

void to_array(int a, int array[])
{
    for (int i = 0; i < b; i++)
    {
        array[i] = a % 6;
        a /= 6;
    }
}

void to_num(int &a, int array[])
{
    a = 0;
    for (int i = b - 1; i >= 0; i--)
    {
        a += array[i];
        a *= 6;
    }
    a /= 6;
}

int reduce_state(int item[], int reduce[])
{
    for (int i = 0; i < b; i++)
        if (item[i] < reduce[i])
            return 0;
    for (int i = 0; i < b; i++)
        item[i] -= reduce[i];
    return 1;
}

const int maxp = 6*6*6*6*6;

int f[maxp];

int dp()
{
    for (int i = 0; i < maxp; i++)
        f[i] = maxint;
    int start;
    to_num(start, num);
    int start_price = 0;
    for (int i = 0; i < b; i++)
        start_price += num[i] * price[i];
    f[start] = start_price;
    for (int i = start; i >= 0; i--) if (f[i] < maxint)
    {
        int now_num[maxn];
        for (int j = 0; j < s; j++)
        {
            to_array(i, now_num);
            if (reduce_state(now_num, reduce[j]))
            {
                int t;
                to_num(t, now_num);
                f[t] <?= f[i] - reduce_price[j];
            }
        }
    }
    int ret = maxint;
    for (int i = 0; i <= start; i++)
        ret <?= f[i];
    return ret;
}

int main()
{
    scanf("%d", &b);
    memset(mark, -1, sizeof(mark));
    for (int i = 0; i < b; i++)
    {
        int t;
        scanf("%d", &t);
        mark[t] = i;
        scanf("%d%d", &num[i], &price[i]);
    }
    scanf("%d", &s);
    for (int i = 0; i < s; i++)
    {
        int t;
        scanf("%d", &t);
        int t1, t2, sum = 0;
        for (int j = 0; j < t; j++)
        {
            scanf("%d%d", &t1, &t2);
            reduce[i][mark[t1]] = t2;
            sum += price[mark[t1]] * t2;
        }
        scanf("%d", &t);
        reduce_price[i] = sum - t;
    }
    printf("%d\n", dp());
    return 0;
}