洛谷/USACO 商店购物 Shopping Offers

洛谷题号:P2732
实在是被这五维的完全背包恶心了一把……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int s, b;
int dp[6][6][6][6][6];
int goods[1000];
int buy[6];
struct plan{
    int n;
    int k[6];
    int p;
}plans[200];
int No = 0;
int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    for (int i = 1; i <= s; i++){
        cin >> plans[i].n;
        for (int j = 1; j <= plans[i].n; j++){
            int ci, ki;
            cin >> ci >> ki;
            if (goods[ci] == 0)goods[ci] = ++No;
            plans[i].k[goods[ci]] = ki;
        }
        cin >> plans[i].p;
    }
    cin >> b;
    for (int i = 1; i <= b; i++){
        int ci, pi, ki;
        cin >> ci >> ki >> pi;
        if (goods[ci] == 0)goods[ci] = ++No;
        buy[goods[ci]] = ki;
        s++;
        plans[s].n = 1;
        plans[s].k[goods[ci]] = 1;
        plans[s].p = pi;
    }
    memset(dp, 0x7f, sizeof(dp));
    dp[0][0][0][0][0] = 0;
    for (int z = 1; z <= s; z++){
        for (int i = plans[z].k[1]; i <= buy[1]; i++){
            for (int j = plans[z].k[2]; j <= buy[2]; j++){
                for (int l = plans[z].k[3]; l <= buy[3]; l++){
                    for (int x = plans[z].k[4]; x <= buy[4]; x++){
                        for (int y = plans[z].k[5]; y <= buy[5]; y++){
                            dp[i][j][l][x][y] = min(dp[i][j][l][x][y], dp[i - plans[z].k[1]][j - plans[z].k[2]][l - plans[z].k[3]][x - plans[z].k[4]][y - plans[z].k[5]]+plans[z].p);
                        }
                    }
                }
            }
        }
    }
    cout << dp[buy[1]][buy[2]][buy[3]][buy[4]][buy[5]] << endl;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注