1000ms

Difficulty: 6

所属公司 : 美团

时间 :2025年9月13日-算法岗

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路

1. 问题分析与转化

对于每个盒子 $j$ ，我们需要找到满足条件的非空子集 $\mathbb{S}$ 的数量。盒子的尺寸为 $(w_j, l_j, h_j)$ 。我们令 $W_j = \min(w_j, l_j)$ 和 $H_j = h_j$ 。条件可以重写为：

$\max_{i \in \mathbb{S}} f_i \leq W_j$
$\sum_{i \in \mathbb{S}} f_i \leq H_j$

题目内容

给定 $n$ 个 $Fibonacci$ 立方体，第 $i$ 个立方体的边长为 $f_i，f_i$ 为 $Fibonacci$ 数列的第 $i$ 项，其中 $Fibonacci$ 数列定义如下：

$f_1=1,f_2=2,f_i=f_{i-1}+f_{i-2}(i>2)$

现有 $m$ 个空盒子，第 $j$ 个盒子的尺寸为宽度 $w_j$ 、长度 $l_j$ 和高度 $h_j$ 。