题意：给你一个人要跑的分钟数n和他的疲劳值m，每一分钟他可以选择休息或者是跑步，每一分钟可以跑的距离给出。
1.如果跑步，那么他的疲劳值就会增加1，最大不超过m,也就是说到达m后他必须休息
2.如果休息，那么他的疲劳值就会减少1，最小到0，但到0后他可以继续休息，保持0不变
要求最后达到n分钟后这个人的疲劳值必须是0，求这个人可以跑的最大距离
思路：咋一看这个题，有点贪心的感觉，有点懵。但其实是个区间dp。
好，接下来我们来确定一下状态含义，这个人跑动距离跟分钟有关同时跟疲劳值也有关，所以我们用dp[i][j]表示第i分钟，疲劳值为j时的最大距离（有没有背包的感觉），那么最后输出什么呢，当然是dp[n][0]（n分钟，疲劳值为0）的状态了！
首先每一个分钟都可以达到m个不同的疲劳值，所以：
（1）第i分钟如果我是从以前跑过来的：dp[i][j] = max(dp[i][j] , dp[i-1][j-1] + d[i])
(2)主要是更新一下dp[i][0]（结果最优处） ： dp[i][0]有两种可能：
a. 一直休息过来的：dp[i][0] = dp[i-1][0]
b.以前运动着休息过来的： dp[i][0] = max(dp[i][0] , dp[i-k][k])(休息完k疲劳值）
代码：
#include <iostream> #include<cstdio> #include<cstring> using namespace std; int dp[10005][505]; int d[10005]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 1;i<=n;i++){ scanf("%d",&d[i]); } memset(dp,0,sizeof(dp)); for(int i = 1;i<=n;i++){//从第1分钟开始 for(int j = 1;j<=m;j++){//现列举跑着来的时候 dp[i][j] = dp[i-1][j-1]+d[i]; } dp[i][0] = dp[i-1][0];//一直休息的时候 for(int k = 1;k<=m&&i-k>=0;k++){//运动着休息的时候 dp[i][0] = max(dp[i][0],dp[i-k][k]); } } printf("%d\n",dp[n][0]); return 0; }