【题目描述】 奶牛Bessie有N分钟时间跑步，每分钟她可以跑步或者休息。若她在第i分钟跑步，可以跑出D_i米，同时疲倦程度增加1（初始为0）。若她在第i分钟休息，则疲倦程度减少1。无论何时，疲倦程度都不能超过M。另外，一旦她开始休息，只有当疲惫程度减为0时才能重新开始跑步。在第N分钟后，她的疲倦程度必须为0。 【输入格式】 第一行，两个整数，代表N和M。 接下来N行，每行一个整数，代表D_i。 【输出格式】 Bessie想知道，她最多能跑的距离。 【样例输入】 5 2 5 3 4 2 10 【样例输出】 9 【数据范围】 N <= 2000 , M <= 500 , D_i <= 1000 【分析】 设f[i][j]表示前i分钟，疲惫值为j时的最优解。 于是对于f[i][]有三种情况： ①继续跑，即f[i][j]=f[i-1][j-1]+d[i] ②在之前疲惫值已经到0了，但是这一分钟仍然休息（好懒的奶牛），即f[i][0]=f[i-1][0] ③从之前的某时开始一直休息，此时（第i分钟）也休息且疲惫值正好为0，即f[i][j]=max(f[i-k][k]){k=1..i} 提示：记得考虑f[i][0]由f[k][0]转移来的情况喔~
这题有一点比较猥琐，就是一休息就要休息到疲劳值为0（奶牛果然没有人类勤奋啊）。辣么如果不让奶牛休息，这题是不是好解的多呢？任何一个蒟蒻都可以看出，f[i][j]=f[i-1][j-1]+d[i]。现在加入了休息也很好办，一休息就去替换f[][0]，而不参加循环部分的运算，这样可以减去一些负担。
于是我们可以写出伪代码：
f[0,0]:=0; for i:=1 to m do f[0,i]:=-maxlongint; for i:=1 to n do f[i,m+1]:=-maxlongint; for i:=1 to n do begin for j:=m downto 1 do begin f[i,j]:=f[i-1,j-1]+d[i]; f[i+j,0]=max(f[i+j,0],f[i-1,j+1]); end; f[i,0]:=max(f[i,0],f[i-1,j],f[i-1,j+1]); end;转载于:https://www.cnblogs.com/JRX2015U43/p/6533517.html
