[USACO08JAN] Running S

需要进行 (n) 分钟的晨跑，在第 (i) 分钟内可以跑 (d_i) 米，疲劳度会增加 (1)，无论何时疲劳度不能超过 (m)，休息一分钟疲劳度会减少 (1)，休息就必须要休息到疲劳度为 (0)，疲劳度恢复到 (0) 就不会继续下降。初态下疲劳度为 (0)。结束时疲劳度也必须恢复到 (0)。求最多能跑多远。(n leq 10^4, d_i leq 1000, m leq 500)

Solution

设 (f[i][j]) 表示考虑前 (i) 分钟，结束时疲劳度为 (j)，所能获得的最大距离，转移时决策这一秒是跑还是开始休息即可

读错题毁一生

#include <bits/stdc++.h>
using namespace std;

const int N = 20005;
int n,m,d[N],f[N][505];

void sh(int &x,int y) {
    x=max(x,y);
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++) {
            sh(f[i][j+1],f[i-1][j]+d[i]);
            if(j==0) sh(f[i][j],f[i-1][j]);
            sh(f[i+j-1][0],f[i-1][j]);
        }
    }
    cout<<f[n][0];
}