题目
Description
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行 n 分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。
贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第 i 分钟内跑步，她可以在这一分钟内跑 di 米，并且她的疲劳度会增加 1。不过，无论何时贝茜的疲劳度都不能超过 m。
如果贝茜选择休息，那么她的疲劳度就会每分钟减少 1，但她必须休息到疲劳度恢复到 0 为止。在疲劳度为 0 时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为 0 。
还有，在 n 分钟的锻炼结束时，贝茜的疲劳度也必须恢复到 0，否则她将没有足够的精力来对付这一整天中剩下的事情。
请你计算一下，贝茜最多能跑多少米。
Input
第一行两个正整数 n,m。
接下来 n 行，每行一个正整数 di。
Output
输出一个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离。
Sample Input
5 2 5 3 4 2 10
Sample Output
9
Hint
【数据范围】
对于 100% 的数据，1≤n≤10^4，1≤di≤1000，1≤m≤500。
【样例说明】
贝茜在第 1 分钟内选择跑步（跑了 5 米），在第 2 分钟内休息，在第 3 分钟内跑步（跑了 4 米），剩余的时间都用来休息。
因为在晨跑结束时贝茜的疲劳度必须为0，所以她不能在第 5 分钟内选择跑步。
最终跑的总距离为 9。
思路
很明显的一道$dp$ 题；
我们可以设$dp[i][j]$ 表示第 $i$ 分钟内，疲劳值为 $j$ ，跑的最大距离；
那么就有三个转移方程：
$1$,不休息 ，第$i$ 分钟跑 $d[i]$ 距离；
$dp[i][j]=max(dp[i][j],dp[i-1][j-1]+d[i]) $;
$2$,第 $i$分钟在休息，疲劳值为$0$ ,第$i-1$ 分钟疲劳值可能为 $0$;(题目允许疲劳值为 $0$ 的时候也休息）
$dp[i][0]=max(dp[i][0],dp[i-1][0])$;
$3$,第 $i$分钟在休息，疲劳值为$0$ ,说明第$i$ 分之前一直休息到疲劳值为 $0$;(题目要求休息必须休息到，疲劳值为 $0$ )
$dp[i][0]=max(dp[i][0],dp[i-j][j])$;
这样就 $ok$ 了；
代码
#include<bits/stdc++.h> #define re register typedef long long ll; typedef unsigned long long ull; using namespace std; inline ll read() { ll a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') c=getchar();} while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();} return a*f; } ll n,m; ll d[10001]; ll dp[10001][501]; int main() { n=read(); m=read(); for(re ll i=1;i<=n;i++) d[i]=read();//读入 for(re ll i=1;i<=n;i++) { dp[i][0]=max(dp[i][0],dp[i-1][0]); //第 i分钟在休息，疲劳值 0 ,第 i-1 分钟疲劳值可能为 0; for(re ll j=0;j<=min(i,m);j++) { if(j)//不休息 ，第 i 分钟跑 d[i] 距离 dp[i][j]=max(dp[i][j],dp[i-1][j-1]+d[i]); if(i-j)//第 i 分之前一直休息到疲劳值为 0; dp[i][0]=max(dp[i][0],dp[i-j][j]); } } ll ans=0; for(re ll i=1;i<=n;i++) ans=max(ans,dp[i][0]);//统计答案 printf("%lld ",ans);//输出 //return 0; }