来源:JZOJ
题目描述
你有一个猪圈,有 N N N 头猪,每天你最多可以杀一头猪卖钱,收益就是猪的体重。但是每过一天猪的体重都会下降 P i Pi Pi,问 K K K 天内你的最大获利。
解题思路
- 这是一道纯粹的 01 01 01 背包,就是要处理一个细节:猪的体重会下降;
- 首先,要按体重下降速度排序,下降快的肯定得先处理呀,不然猪的体重就变负数了(“死”了 Q A Q QAQ QAQ)
- 然后,就是一个板子吧,不过状态转移方程得注意一个小细节,如果杀猪,得保证猪的体重大于 0 0 0,只要