会员专享
请先
登录 ，登录后可使用今日免费解锁；
开通会员 后可解锁完整内容。
解题思路
核心思路：把每个任务维度看成一「组」物品，组内候选适配器互斥（至多启用一个），整组也可以不启用；显存预算 M M M f i [ j ] f_i[j] f i [ j ] i i i j j j i i i f i − 1 [ j ] f_{i-1}[j] f i − 1 [ j ] ( w , v ) (w, v) ( w , v ) 组前状态 做转移 f i [ j ] = max ( f i [ j ] , f i − 1 [ j − w ] + v ) f_i[j] = \max(f_i[j],\, f_{i-1}[j-w] + v) f i [ j ] = max ( f i [ j ] , f i − 1 [ j − w ] + v )
实现方法：滚动数组。每组开始前复制一份组前状态 pre，组内每个候选从 pre[j-w] 转移更新 f[j]；容量维度无需逆序，因为读取的是 pre（冻结副本）。w > M w > M w > M f f f 0 0 0 dfs(i, 剩余显存)：不启用本组继承 dfs(i+1, cap)，再枚举组内每个候选 dfs(i+1, cap-w) + v 取最大，两者答案一致。
复杂度分析
时间复杂度 O ( M × ∑ k i ) O(M \times \sum k_i) O ( M × ∑ k i ) M = 500 M = 500 M = 500 ∑ k i = 1000 \sum k_i = 1000 ∑ k i = 1000 5 × 10 5 5 \times 10^5 5 × 1 0 5 60 60 60 O ( M ) O(M) O ( M ) O ( N × M ) O(N \times M) O ( N × M )
题目内容
某团队将基座大模型部署到端侧设备，通过挂载 LoRA 适配器补齐不同任务维度的能力。共有 N N N i i i k i k_i k i j j j w i , j w_{i,j} w i , j v i , j v_{i,j} v i , j
设备总显存预算为 M M M 至多启用一个 适配器，也可以整组不启用。所有启用适配器的显存占用之和不得超过 M M M
选择规则
每个适配器只有启用、不启用两种状态，且至多启用一次。
同一维度下的候选适配器互斥，最多启用其中一个。
未启用的适配器不占用显存、不贡献提升分。
解答要求
时间限制：C/C++ 1000ms，其他语言：2000ms
内存限制：C/C++ 512MB，其他语言：1024MB
输入描述
第一行：2 个用空格分隔的整数 N N N M M M
接下来 N N N i i i k i k_i k i k i k_i k i w w w v v v
约束
1 ≤ N ≤ 100 1 \le N \le 100 1 ≤ N ≤ 100 1 ≤ M ≤ 500 1 \le M \le 500 1 ≤ M ≤ 500 1 ≤ k i 1 \le k_i 1 ≤ k i k i k_i k i 1000 1000 1000 1 ≤ w ≤ 500 1 \le w \le 500 1 ≤ w ≤ 500 0 ≤ v ≤ 10 4 0 \le v \le 10^4 0 ≤ v ≤ 1 0 4
输出描述
输出一个整数，表示能力提升分之和的最大值。
样例1
输入
3 10
3
3 4
5 8
10 10
2
4 5
6 9
2
2 3
5 5
输出
13
说明
选维度 1 的适配器 ( 3 , 4 ) (3,4) ( 3 , 4 ) ( 6 , 9 ) (6,9) ( 6 , 9 ) 3 + 6 = 9 ≤ 10 3+6=9 \le 10 3 + 6 = 9 ≤ 10 4 + 9 = 13 4+9=13 4 + 9 = 13 ( 7 , 10 ) (7,10) ( 7 , 10 ) 10 10 10 13 13 13
样例2
输入
3 6
2
3 5
4 7
2
5 3
6 4
2
2 2
4 6
输出
9
说明
选维度 1 的适配器 ( 4 , 7 ) (4,7) ( 4 , 7 ) ( 2 , 2 ) (2,2) ( 2 , 2 ) 4 + 2 = 6 4+2=6 4 + 2 = 6 7 + 2 = 9 7+2=9 7 + 2 = 9
