题目描述

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　张超来到了超市购物。
　　每个物品都有价格，正好赶上商店推出促销方案。就是把许多东西一起买更便宜（保证优惠方案一定比原价便宜）。物品要买正好的个数，而且不能为了便宜而买不需要的物品。
　　张超拿到了优惠方案，和需要购买的物品清单，当然想求出最小的花费。他是信息学选手，自然地想到写个程序解决问题。
输入格式
　　第一行促销物品的种类数（0 <= s <= 99）。
　　第二行..第s+1 行每一行都用几个整数来表示一种促销方式。
　　第一个整数 n （1 <= n <= 5），表示这种优惠方式由 n 种商品组成。
　　后面 n 对整数 c 和 k 表示 k （1 <= k <= 5）个编号为 c （1 <= c <= 999）的商品共同构成这种方案。
　　最后的整数 p 表示这种优惠的优惠价（1 <= p <= 9999）。也就是把当前的方案中的物品全买需要的价格。
　　第 s+2 行这行一个整数b （0 <= b <= 5），表示需要购买 b 种不同的商品。
　　第 s+3 行..第 s+b+2 行这 b 行中的每一行包括三个整数：c ，k ，和 p 。
　　C 表示唯一的商品编号（1 <= c <= 999），
　　k 表示需要购买的 c 商品的数量（1 <= k <= 5）。
　　p 表示 c 商品的原价（1 <= p <= 999）。
　　最多购买 5*5=25 个商品。
输出格式
　　一个整数ans，表示需要花的最小费用

样例

样例输入

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

样例输出

14

Tips：

1.把目前买了多少个该物品当作一种状态，而最优方案就是花费最小的那个；
2.因为活动一定比单件物品单买优惠，所以把目前买了多少个该物品当作一种状态时
最大值就应该是所有物品都是按原价买的值，若当前买的物品符合某种方案，就与当前
状态的值比较（可能这种方案的前一种方案也满足当前状态，所以目前的活动方案不是最优解）

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>

struct kk { int thing, num; };
std::vector<struct kk>ali[1000 + 7];
int pay[1000 + 7] = {};
int S, want;
int buy[7], money[7], num[7];
int dp[1][7][7][7][7][7] = { {{{{{}}}}} };//除了dp[0]无意义外，其它表示第n个商品当前买了x件表示

int main(void)
{
    std::ios_base::sync_with_stdio(false);
    std::cin >> S;
    for (int i = 1; i <= S; i++)
    {
        int cx;
        std::cin >> cx;
        while (cx--)
        {
            int thing, num;
            std::cin >> thing >> num;
            ali[i].push_back({ thing,num });
        }
        std::cin >> pay[i];
    }

    std::cin >> want;
    for (int i = 1; i <= want; i++)std::cin >> buy[i] >> num[i] >> money[i];
    int data[7] = {};
    //for (int i = 1; i <= want; i++)post[i] = &data[i];

    for (data[1] = 0; data[1] <= num[1]; data[1]++)
        for (data[2] = 0; data[2] <= num[2]; data[2]++)
            for (data[3] = 0; data[3] <= num[3]; data[3]++)
                for (data[4] = 0; data[4] <= num[4]; data[4]++)
                    for (data[5] = 0; data[5] <= num[5]; data[5]++)
                    {
                        dp[0][data[1]][data[2]][data[3]][data[4]][data[5]]
                            = data[1] * money[1] + data[2] * money[2] + data[3] * money[3] + data[4] * money[4] + data[5] * money[5];//无方案满足的话，这就是那个状态的最优解了
                        for (int i = 1; i <= S; i++)
                        {
                            int flag = 1;
                            int buy_now[6] = {};

                            for (int m = 0; m < ali[i].size(); m++)
                            {
                                int is = 0;
                                for (int n = 1; n < 6; n++)
                                    if (buy[n] == ali[i][m].thing && data[n] >= ali[i][m].num)buy_now[n] += ali[i][m].num, is = 1;
                                    else if (buy[n] == ali[i][m].thing && data[n] < ali[i][m].num)
                                    {
                                        flag = 0;
                                        break;
                                    }
                                if (!is || !flag)
                                {
                                    flag = 0;
                                    break;
                                }
                            }
                            if (flag)
                            {
                                dp[0][data[1]][data[2]][data[3]][data[4]][data[5]]
                                    = std::min(dp[0][data[1]][data[2]][data[3]][data[4]][data[5]], dp[0][data[1] - buy_now[1]][data[2] - buy_now[2]][data[3] - buy_now[3]][data[4] - buy_now[4]][data[5] - buy_now[5]] + pay[i]);
                                    //若有方案满足，比较选择最优解；
                            }
                        }

                    }

    std::cout << dp[0][num[1]][num[2]][num[3]][num[4]][num[5]];
    return 0;
}