洛谷题号: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; } |