The 6th Zhejiang Provincial Collegiate Programming Contest

Problem J

这个题目,有难度!

沙茶题留名……

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

就是DP

先按每日消耗时间的顺序从大到小排

F表示DP到前I棵树用了J天的最大值

单调性证明:

比较两棵消耗速度分别为V1,V2,总价值为C1,C2的树

令V1>V2,若在两树都一定要取的情况下,且间隔P天,之前过了T天

若先取V1,获利为S1=C1+C2-P*V1-T*(V1+V2);

若先取V2,获利为S2=C2+C1-P*V2-T*(V1+V2);

S1一定大于S2

故...........

Orz

膜拜

sf & orz voyagec 的题目