题解 P2732 【商店购物 Shopping Offers】

· · 题解

感觉楼下的题解有些欠缺来补充一下。

首先先讲几个坑点

1.所有优惠方案里不会出现别的物品，所以不要想多，大力搞就行了

2.优惠方案可以多次使用，所以for不用倒过来，这点希望大家注意，我就是没注意第一次按01背包只有41分。

个人感觉我的做法比较好理解，可以给大家提供一点思路。

首先你先观察，发现要你买的物品只有五种，而且所有的优惠方案里没有别的物品，你就只要把编号对应到1.2.3.4.5里就行了，看代码注释

#include<cstdio>
#include<algorithm>
#include<cctype>
#define N (20010)
using namespace std;
int s, n;
int d[N], need[N], pri[N], f[10][10][10][10][10];//f为dp数组，pri为价格，need表示需要几个
int read(){
    int t = 0;
    char p = getchar();
    while(!isdigit(p)) p = getchar();
    do{
        t = t * 10 + p - 48; 
        p = getchar();  
    }while (isdigit(p));
    return t;
} //快读，打习惯了
struct item{
    int id[100], num[100], v, tot, fin[100];
}q[N];//表示每一个优惠政策
int main(){
    s = read();
    for (int i = 1; i <= s; i++){
        int tot = read();
        q[i].tot = tot;
        for (int j = 1; j <= tot; j++){
            q[i].id[j] = read();
            q[i].num[j] = read();
        }
        q[i].v  = read();
    } 
    n = read();
    for (int i = 1; i <= n; i++){
        int num = read();
        d[num] = i;//d表示我对应的几号物品是1.2.3.4.5中的哪一个
        need[i] = read(), pri[i] = read();
    } 
    for (int i1 = 0; i1 <= need[1]; i1++)    
    for (int i2 = 0; i2 <= need[2]; i2++)
    for (int i3 = 0; i3 <= need[3]; i3++)
    for (int i4 = 0; i4 <= need[4]; i4++)
    for (int i5 = 0; i5 <= need[5]; i5++){
        f[i1][i2][i3][i4][i5] = i1 * pri[1] + i2 * pri[2] + i3 * pri[3] + i4 * pri[4] + i5 * pri[5];

}//其实我觉得其他题解把单独选的也当dp做，有点杀鸡用牛刀，其实只要预处理一下就行了

    for (int i = 1; i <= s; i++){
        for (int j = 1; j <= q[i].tot; j++) q[i].fin[d[q[i].id[j]]] = q[i].num[j];
    }
    for (int i = 1; i <= s; i++){
        for (int i1 = q[i].fin[1]; i1 <= need[1]; i1++)
        for (int i2 = q[i].fin[2]; i2 <= need[2]; i2++)
        for (int i3 = q[i].fin[3]; i3 <= need[3]; i3++)
        for (int i4 = q[i].fin[4]; i4 <= need[4]; i4++)
        for (int i5 = q[i].fin[5]; i5 <= need[5]; i5++)
            f[i1][i2][i3][i4][i5] = min(f[i1][i2][i3][i4][i5], f[i1-q[i].fin[1]][i2-q[i].fin[2]][i3-q[i].fin[3]][i4-q[i].fin[4]][i5-q[i].fin[5]] + q[i].v);
    }//dp转移，其实很水，就是一个模拟离散化的过程有点难想
    printf("%d", f[need[1]][need[2]][need[3]][need[4]][need[5]]);
    return 0;
}
希望大家注意坑点，a题越来越顺利！