题目链接~~>
做题感悟:开始感觉写的很对,但是生成数据后就发现不对了,于是改为先求出安全度,再求最小费用。
解题思路:
先 dp 解出安全度,状态转移方程: dp[ i ] [ j ] = max( dp[ i ][ j ] ,min( dp[ i - k ][ j - 1 ] ,g[ j ] / k ) )
, ( 0 <= k <= i ,0 时特判) 表示枚举 j 管理几个仓库。这样就求出安全度,然后用背包处理一下,转化为容量为个数,价值为个人能力对安全度取余,这样计算最小的费用的时候即为:容量 * 安全度 + 对应的价值,容量大于等于 n ,这样就可以求出最小的费用了......
阅读全文