luogu P1353 【[USACO08JAN]跑步Running】

USACO!!! 唉！无一例外又是母牛（终于知道美国的牧场养什么了）

---

今天的主人公是一个叫贝茜的公主病母牛（好洋气） 可是她叫什么和我们理解题好像没有什么关系

通过读题我们可以发现她有三个傲娇的地方

1.她要继续走

2.她要中途休息，但是要休息到完全恢复体力，即疲劳度为0

3.她要发奋图强一直走下去，直到体力耗尽

那么我们针对这三种情况就可以发现有三个状态转移方程式

1.她要继续走那么疲劳度+1，再加上这一秒所走的距离 f[i-1][j-1]+a[i]

2.她要中途休息，那么疲劳度休息到0，距离不变 f[i+j][0],f[i-1][j+1]

3.她一直走直到体力耗尽，必须恢复疲劳度，那么她会一直休息 f[i][j],f[i-1][0]

#include<bits/stdc++.h>
using namespace std;
const int M = 11000;
int n,m;
int a[M],f[M][510];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
        {
            if(i+j<=n)
                f[i+j][0]=max(f[i+j][0],f[i-1][j+1]);
            if(j==0)
                f[i][j]=max(f[i][j],f[i-1][0]);
            else
                f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
        }
    cout<<f[n][0]<<endl;
    return 0;
}