题目大意：有一个人要买b件商品，给出每件商品的编号，价格和数量，恰逢商店打折。有s种打折方式。问怎么才干使买的价格达到最低

解题思路：最多仅仅有五种商品。且每件商品最多仅仅有5个，所以能够用5维dp来表示。每一个维度都代表一件商品的数量

打折的方式事实上有b + s种。将每种商品单件卖的也算一种打折方式

这题有个坑点，就是b或者s有可能为0

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define maxn 6

#define maxs 200

#define INF 0x3f3f3f3f

struct product{

    int c, k, p;

}pro[maxn];

struct offer{

    int num[maxn], price;

}off[maxs];

int b, s;

int dp[maxn][maxn][maxn][maxn][maxn];

map<int,int> m;

void init() {

    memset(dp, -1, sizeof(dp));

    memset(off, 0, sizeof(off));

    m.clear();

    for(int i = 0; i < b; i++) {

        scanf("%d%d%d", &pro[i].c, &pro[i].k, &pro[i].p);

        m[pro[i].c] = i;

        off[i].num[i] = 1;

        off[i].price = pro[i].p;

    }

    if(b < 5) {

        for(int i = b; i < 5; i++)

            pro[i].k = pro[i].p = 0;

    }

    scanf("%d", &s);

    int n, c, k;

    for(int i = b; i < b + s; i++) {

        scanf("%d", &n);

        for(int j = 0; j < n; j++) {

            scanf("%d%d", &c, &k);

            off[i].num[m[c]] += k;

        }

        scanf("%d", &off[i].price);

    }

}

int dfs(int a1, int a2, int a3, int a4, int a5) {

    if(dp[a1][a2][a3][a4][a5] != -1)

        return dp[a1][a2][a3][a4][a5];

    dp[a1][a2][a3][a4][a5] = INF;

    for(int i = 0; i < b + s; i++) {

        if(a1 >= off[i].num[0] && a2 >= off[i].num[1] && a3 >= off[i].num[2]  && a4 >= off[i].num[3] && a5 >= off[i].num[4])

            dp[a1][a2][a3][a4][a5] = min(dp[a1][a2][a3][a4][a5], off[i].price + dfs(a1-off[i].num[0],a2-off[i].num[1],a3-off[i].num[2],a4-off[i].num[3],a5-off[i].num[4]));

    }

    return dp[a1][a2][a3][a4][a5];

}

void solve() {

    dp[0][0][0][0][0] = 0;

    if(b == b + s) {

        int t = 0;

        for(int i = 0; i < 5; i++)

            t += pro[i].p * pro[i].k;

        printf("%d\n", t);

    }

    else

        printf("%d\n",dfs(pro[0].k, pro[1].k, pro[2].k, pro[3].k, pro[4].k));

}

int main() {

    scanf("%d", &b);

    init();

    solve();

    return 0;

}