描述 Description
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行 N(1 <= N <= 10,000) 分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第 i 分钟内跑步，她可以在这一分钟内跑 D_i(1 <= D_i <= 1,000) 米，并且她的疲劳度会增加 1。不过，无论何时贝茜的疲劳度都不能超过 M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少 1，但她必须休息到疲劳度恢复到 0 为止。在疲劳度为 0 时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为 0。 还有，在 N 分钟的锻炼结束时，贝茜的疲劳度也必须恢复到 0，否则她将没有足够的精力来对付这一整天中剩下的事情。 请你计算一下，贝茜最多能跑多少米。
输入格式 InputFormat
第 1 行: 2 个用空格隔开的整数：N 和 M.
第 2..N+1 行: 第 i+1 为 1 个整数：D_i.
输出格式 OutputFormat
第 1 行: 输出 1 个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离.
样例输入 SampleInput
8 1
1
8
2
7
3
6
4
5
## 样例输出 SampleOutput 21
数据范围和注释 Hint
贝茜在第 1 分钟内选择跑步（跑了 5 米），在第 2 分钟内休息，在第 3 分钟内跑步（跑了 4 米），剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须为 0，所以她不能在第 5 分钟内选择跑步。
代码 Code
用 f[i][j] 表示第 i 分钟疲倦程度为 j 的最大跑动距离. 另外 Tyvj 和 BZOJ 上的数据范围竟然是不一样的。。。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int d[10001];
int f[10001][501];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&d[i]);
for (i=1;i<=n;i++)
{
f[i][0]=f[i-1][0];
for (t=1;t<=i;t++) if (t>m) break;
else
{
f[i][0]=max(f[i][0],f[i-t][t]);
}
for (j=1;j<=m;j++) f[i][j]=f[i-1][j-1]+d[i];
}
printf("%d\n",f[n][0]);
return 0;
}program nndl1023;
var d:array[1.. 10000]of longint;
f:array[0.. 10000,0.. 500]of longint;
i,j,t,n,m,l,r,z,y,x:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(n,m);
for i:=1 to n do readln(d[i]);
for i:=1 to n do
begin
f[i,0]:=f[i-1,0];
for t:=1 to i do if t>m then break else
begin
f[i,0]:=max(f[i,0],f[i-t,t]);
end;
for j:=1 to m do f[i,j]:=f[i-1,j-1]+d[i];
end;
writeln(f[n,0]);
end.