题目描述
What is the length of the shortest pipe, of internal radius $50$mm, that can fully contain $21$ balls of radii $30$mm, $31$mm, …, $50$mm?
Give your answer in micrometres ($10^{-6}$ m) rounded to the nearest integer.
题意
让你在一个内径$50$的圆管里塞$21$个内径分别为$31-50$的小球,问你圆管最短是多少
分析
比较显然是dp
考虑dp状态:dp[i][j]表示选择小球对应的集合为j,并且用第i个小球结尾,然后我们转移的时候就直接添加一个小球,对于剩余的小球枚举一个结尾,取最优解就行了
代码
给大佬递上我奇丑无比的代码 (/ω\)
1 |
|