题解 P1717 【钓鱼】

· · 题解

看到这题，贪心不会，考虑dp。

设 f[i][j] 为佳佳经过前i个湖消耗j时间所获得的最多鱼数。

背包建模，开始dp。

他从哪里来？

从上一个湖那里来。

要到哪里去？

要到下一个湖去，或者在这个湖钓鱼。

于是得出dp方程： f[i][j]=max( k*( p[i].num+p[i].num-p[i].reduce*( k-1 ) )/2+f[i-1][j-k] )

完成。