dp[i][j]:第i分钟疲劳度为j时的最大路径值
转移方程：
dp[i][j] = dp[i - 1][j - 1] + distance[i] ( j > 0 )
dp[i][0] = max (dp[i - 1][0], dp[i - j][j](i - j >= j && j <= M))
1
#include <cstdio>
2
3
const int SIZE_T = 10001;
4
const int SIZE_M = 501;
5
6
int dp[SIZE_T][SIZE_M];
7
8
int T, M, dist[SIZE_T];
9
10
void 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
35
int 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
}