解决该题的思路就是如何建立状态就保留所有的解（包括临时解）这很简单，该题只是对于某一分钟走或者是休息，而这也只改变其疲劳值，因此开一个二维数组第一维表示该走到了第几分钟，第二维表示疲劳值，保留的值为能够走得最远距离。该题还有一个地方要注意就是疲劳值为零的状态的来源有多个，可以是原来疲劳值为0,1以及能够休息到该分钟为零的任意前面一分钟。
f[i][j] 表示第i分钟疲劳值为j能够走得最远距离。
f[i][0] = max(f[i-1][0], f[i-k][k]) 其中 1 <= k <= i /2, 因为i-k >= k;
f[i][j] (j != 0) = f[i-1][j-1]+seq[i];
代码如下：
#include <cstring> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #define MAXN 20005 using namespace std; /* 定义如何的状态，才能够使得问题得到解决 ? ? ? 决定该题的解的影响因素是在第i分针是选择休息还是跑步 那么第i分钟的决定于前面的最优状态的有什么关系 确定一个二维数组，用来保留第i分钟疲劳值为任意值所能够 前进的最远距离. 5 2 5 3 4 2 10 // 要是休息的话，那么就一直休息，直到疲劳值为零 */ int N, M, seq[MAXN]; int dp[MAXN][505]; void DP() { memset(dp, 0, sizeof (dp)); for (int i = 1; i <= N; ++i) { for (int j = 0; j <= M; ++j) { if (j == 0) { dp[i][j] = dp[i-1][j]; for (int k = 1; k <= i>>1; ++k) { dp[i][j] = max(dp[i][j], dp[i-k][k]); } } else { dp[i][j] = dp[i-1][j-1]+seq[i]; } } } printf("%d\n", dp[N][0]); } int main() { while (scanf("%d %d", &N, &M) == 2) { for (int i = 1; i <= N; ++i) { scanf("%d", seq+i); } DP(); } return 0; }