对DP答案不在F[n][k]的猜想。

F[i][j]=max(F[i-1][j-1]+val,F[i-1][j])

大多人都是写得这个转移方程吧,但实际上DP的答案并不存在与F[n][k]中,这让人非常有疑问。
答案在F[n][]是没错,问题在与后一维不一定为k,但根据贪心思想"有树就砍,反正有钱"而言,后一维原本是取k无错。
我在此处有2点猜想,但愿能帮到你们,希望有缘人能实现这道题的证明。

1. 树的价值 - 天数 * 掉落量 < 0 , 这告诉我们所有树都取总值反而更小。
2. 掉落量单调 , 但树的价值并不单调 , 会产生后取树的损失(天数 * 掉落量)大于之前取树的情况。

列如一下情况 , 很明显 [8] 的 那组时不必取的:

3 3
8 9 1000
4 3 2

0 条评论

目前还没有评论...

信息

ID
1574
难度
5
分类
动态规划 | 贪心 点击显示
标签
递交数
1012
已通过
324
通过率
32%
被复制
2
上传者