会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题的算法标签是「动态规划」，模型是一个带分组约束的 0/1 背包（分组背包）：每个摄像头是一组，组内可以「不选」或者选某一个 Profile，同一组至多选一个；目标还是双关键字的字典序——先让选中的摄像头数量最多，再让总带宽最小。
第一步：把每个摄像头压缩成一组「代价」。
如果决定接入某个摄像头，一定选它所有「带宽不超过 W」的 Profile 里带宽最小的那个：换更贵的档位只会让数量不变、总带宽变大，约束更紧，永远不会更优。所以先解析配置串，把带宽 >W 的档位直接丢掉，得到该摄像头的可用档位集合；若集合为空，这个摄像头永远不可能被选中，只能是「不选」。DP 里仍按「组内多档」写，天然兼容一个摄像头有多档的语义。
第二步：设计 DP 状态。
题目内容
视频监控系统中，每个摄像头可通过 Profile 配置多种视频流规格（如 1080P30、720P15、VGA30），不同 Profile 对应不同带宽占用（Mbps），画质越好占用带宽越大。
监控中心需要在有限的带宽 W Mbps 内接入摄像头视频流，既要覆盖尽可能多的摄像头，又要尽量节省带宽。现在给定 n 个摄像头及其可选 Profile 列表，为每个摄像头选择一种 Profile 或不选，使得：
- 选中的摄像头数量最多；
- 在选中数量最多的前提下，总带宽占用最小。
记答案为 [maxStreams, minRate]，即 [最大摄像头流数, 最小总带宽]；若一个摄像头都无法接入，输出 [0,0]。
输入描述
输入只有一行，形如：
3,6,["cam01 1080P30 6 720P15 2","cam02 720P30 3 VGA30 1","cam03 VGA30 1"]
即依次给出：
- 摄像头数量
n（整数），后跟一个半角逗号 ,；
- 带宽上限
W（整数），后跟一个半角逗号 ,；
- 摄像头配置列表：用方括号
[] 包住，每个摄像头对应一个用半角双引号 " 包住的字符串，字符串之间用半角逗号分隔。
每个配置串内部用单个空格分隔，格式为「标识 配置名 带宽 配置名 带宽 …」：第一个字段是摄像头标识，之后每两个字段是一组「配置名 带宽」，配置名不含空格，带宽为整数（Mbps）。例如 "cam01 1080P30 6 720P15 2" 表示 cam01 有两档配置：1080P30（6 Mbps）与 720P15（2 Mbps）。
输出描述
输出一行，形如 [maxStreams,minRate]：maxStreams 为最多能接入的摄像头数量，minRate 为在接入数量最多的前提下所需的最小总带宽。若一个摄像头都无法接入，输出 [0,0]。
数据范围
- 1≤n≤100；
- 1≤W≤100000；
- 每个摄像头至少给出 1 个 Profile，至多 10 个 Profile；
- 每个 Profile 的带宽为整数，1≤ 带宽 ≤100000；
- 摄像头标识与配置名均为不含空格、不含双引号的字符串，且同一摄像头内的配置名不重复；
- 输入保证合法，无需做额外校验。
样例1
输入
3,6,["cam01 1080P30 6 720P15 2","cam02 720P30 3 VGA30 1","cam03 VGA30 1"]
输出
[3,4]
说明
三个摄像头均可拉取。三路全选的组合中，cam01 选 720P15(2) + cam02 选 VGA30(1) + cam03 选 VGA30(1) = 4Mbps，3 路为最大流数，4Mbps 为 3 路流下的最小总带宽占用。
样例2
输入
2,10,["cam01 1080P30 6 720P15 2","cam02 1080P30 6 VGA30 1"]
输出
[2,3]
说明
两路都能选的组合：cam01(6)+cam02(1)=7，cam01(2)+cam02(6)=8，cam01(2)+cam02(1)=3。都是 2 路流，但 cam01 选 720P15(2Mbps)+cam02 选 VGA30(1Mbps)=3Mbps 总带宽占用最小。
样例3
输入
2,5,["warehouse 4K30 12","rooftop 1080P30 6"]
输出
[0,0]
说明
两个摄像头唯一 Profile 的带宽占用（12、6Mbps）均超过带宽上限 5Mbps，无法拉取任何流。
