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
|
using namespace std; int n, m, v, k, cost[250], val[250], op, dp1[250][250], dp[250][1005], tmp[250][50]; struct { int to, cnt; vector <int> from; } e[250]; int main() { scanf("%d%d%d%d", &n, &m, &v, &k); for(int i = 1; i <= n; i++) scanf("%d%d", cost + i, val + i); for(int i = 1; i <= m; i++) { scanf("%d%d", &e[i].to, &e[i].cnt); e[i].from.push_back(0); for(int j = 1, x; j <= e[i].cnt; j++) scanf("%d", &x), e[i].from.push_back(x); } for(int i = 1; i <= n; i++) for(int j = 0; j <= k; j++) dp1[i][j] = cost[i]; for(int cnt = 1; cnt <= k; cnt++) for(int i = 1; i <= m; i++) { for(int j = 1; j <= e[i].cnt; j++) { for(int t = 0; t < cnt; t++) { tmp[j][t] = 2e9; for(int tt = 0; tt <= t; tt++) tmp[j][t] = min(tmp[j][t], tmp[j - 1][t - tt] + dp1[e[i].from[j]][tt]); } } dp1[e[i].to][cnt] = min(dp1[e[i].to][cnt], tmp[e[i].cnt][cnt - 1]); } for(int i = 1; i <= n; i++) for(int use = 0; use <= k; use++) { for(int j = use; j <= k; j++) for(int l = dp1[i][use]; l <= v; l++) dp[j][l] = max(dp[j][l], dp[j - use][l - dp1[i][use]] + val[i] - dp1[i][use]); } return cout << dp[k][v] << endl, 0; }
|
近期评论