1 条题解
-
0lhs LV 8 @ 2023-8-7 11:20:10
依赖背包 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <map> #include <cstring> #include <iomanip> const int N = 32000 + 10; const int INF = 0x3f3f3f3f; using namespace std; struct node{ int w , v , w1 ,v1 , w2 , v2; }a[70]; int m , n , dp[N] ,x , y , z; int main() { cin >> m >> n; for(int i = 1 ; i <= n; i++) { cin >> x >> y >> z;//x是价格 y重要度 z主件 if( !z )//主件 { a[i].w = x; a[i].v = x * y; } else//附件 { if(a[z].v1) { a[z].w2 = x; a[z].v2 = x * y; } else { a[z].w1 = x; a[z].v1 = x * y; } } } for(int i = 1 ; i <= n; i++) { if(!a[i].v) continue; for(int j = m; j >= a[i].w; j--) { //考虑 不买 ,买主件 dp[j] = max(dp[j] , dp[j - a[i].w] + a[i].v); if(j >= a[i].w + a[i].w1)//买主 + 附1 dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w1] + a[i].v + a[i].v1); if(j >= a[i].w + a[i].w2)//买主 + 附2 dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w2] + a[i].v + a[i].v2); if(j >= a[i].w + a[i].w1 + a[i].w2)//买主 + 附1 + 附2 dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w1 - a[i].w2] + a[i].v + a[i].v1 + a[i].v2); } } cout << dp[m]; return 0; }
借鉴了张老师的代码
- 1
信息
- ID
- 688
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 99
- 已通过
- 38
- 上传者