Hdu/Hdoj 2670 Girl Love Value

2009-04-27 13:44:16

Accepted

2670

125MS

4204K

870 B

C++

Master Jedi

把问题分为两个子问题：
1.选出哪k个boy；
2.按什么顺序选。
每个boy有两个属性：喜欢度 和 衰减速度。
其中衰减速度是关键。
我的感觉是：最好先选择衰减速度快的人（貌似贪心），好让总的衰减值最小。
因此先按衰减速度递减排序（解决子问题2），再DP（解决子问题1）。
其中f[i][j]表示：从前i个人中 按一定次序选出j个人 得到的最优喜欢度。