COGS-146. [USACO Jan08] 贝茜的晨练计划

好久没有写题解...终于来更新一波...
这题就是一道比较简单的动归...
题目一个比较关键的点就是：如果贝茜选择休息，她必须休息到疲劳度恢复到0为止
所以更新的时候分两种情况
设f[i][j]为第i秒疲劳度为j时的最优解
则f[i][0]=max(f[i][0],f[i-k][k])
f[i][j]=max(f[i][j],f[i-1][j-1]+d[i]) 要注意这里应加d[i]而非d[i-1]
代码如下

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int f[10010][600];
int d[10010];
int n,m;
int main(){
	freopen("cowrun.in","r",stdin);
	freopen("cowrun.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);	
	}
	for(int i=1;i<=n;i++){
		f[i][0]=f[i-1][0];
		for(int j=1;j<=m;j++){
			if(i-j>0)
				f[i][0]=max(f[i][0],f[i-j][j]);       //如果可以由某一秒休息而来，更新 
			f[i][j]=max(f[i-1][j-1]+d[i],f[i][j]);     //更新由前一秒跑步过来 
		}
	}
	printf("%d",f[n][0]);
	return 0;
}