题解 P1353 【[USACO08JAN]跑步Running】

今宵満月 · 2018-03-07 21:38:09 · 题解

看到大家的题解都是“填表法”，在此奉上一篇独特的“刷表法”，供各位老哥参考~

状态是用f[i][j]表示，代表在第i分钟疲劳值为j时跑的最远距离。边界是f[1][0]=0, f[1][1]=d[1]。那么，状态转移方程（刘汝佳前辈曾经教导过我们，刷表法的事，能叫状态转移方程吗？）就是

f[i][0]=max(f[i][0], f[i-1][0]);//这一行一定一定要放在最前面，因为第三个方程只会更新到f[i+j][0]，无法继续向后更新
f[i+j][0]=max(f[i+j][0], f[i][j]);//在当前情况下休息的情况
f[i+1][j+1]=max(f[i+1][j+1], f[i][j]+d[i+1]);//在当前情况下不选择休息的情况

代码如下~

#include<iostream>
#include<cstdio>
using namespace std;

int f[10510][510], n, m, d[10010];

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &d[i]);
    }
    f[1][1]=d[1];
    for(int i=1; i<=n; ++i) {
        for(int j=0; j<=min(i, m); ++j) {
            if(j==0)
                f[i][0]=max(f[i-1][0], f[i][0]);
            else
                f[i+j][0]=max(f[i+j][0], f[i][j]);
            f[i+1][j+1]=max(f[i+1][j+1], f[i][j]+d[i+1]);
        }
    }
    printf("%d", f[n][0]);
    return 0;
}