gzwzm06

 1#include <cstdio>
 2
 3const int SIZE_T = 10001;
 4const int SIZE_M = 501;
 5
 6int dp[SIZE_T][SIZE_M];
 7
 8int T, M, dist[SIZE_T];
 9
10void Solve()
11{
12    int i, j;
13
14    for ( i = 0; i <= M; ++i )
15        dp[0][i] = 0;
16
17    for ( i = 1; i <= T; ++i )
18    {
19        dp[i][0] = dp[i - 1][0];
20        for ( j = 1; i - j >= j && j <= M; ++j )
21        {
22            dp[i][0] = (dp[i][0] > dp[i - j][j] ? dp[i][0] : dp[i - j][j] );
23        }
24
25        for ( j = 1; j <= M; ++j )
26        {
27            dp[i][j] = dp[i - 1][j - 1] + dist[i]; 
28                
29        }
30    }
31    
32    printf("%d\n", dp[T][0]);
33}
34
35int main()
36{
37    int i;
38    scanf("%d %d", &T, &M);
39
40    for ( i = 1; i <= T; ++i )
41        scanf("%d", &dist[i]);
42
43    Solve();
44
45    return 0;
46}