递推更新的就是坑。。。
设\(dp[i][j]\)为第\(i\)分钟，疲劳度为\(j\)的最大跑步距离。
发现了一种叫做“刷表法”的东西。我虽然不知道是什么东西，但是第一次写的时候就是用这种思想。
刷表法就是用已知的信息来更新后面的信息。而想记忆化搜索、普通递推的，叫做填表法。
下面是更新的方法：
你可以休息，连你疲劳度为0也可以。\(dp[i + 1][0] = max(dp[i + 1][0], dp[i][0])\)
疲劳度不为0的时候，设为\(j\)，显然需要\(j\)天才休息好。\(dp[i + j][0] = max(dp[i + j][0], dp[i][j])\)
你可以跑步。\(dp[i + 1][j + 1] = dp[i][j] + d[i + 1]\)（这里注意是\(d[i + 1]\)，因为你更新的是\(i +1\)天的状态）
你疲劳度为m的时候就不能继续跑了，所以上面注意。
坑点
你数组不要只开大5个。不然RE。
即使你最终答案是\(dp[n][0]\)，你\(i\)也要取\(n\)。
你需要先讨论休息，后讨论跑步。
代码：
#include#include const int maxn = 10505, maxm = 505;int dp[maxn][maxm];int d[maxn];int n, m;int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &d[i]); dp[1][0] = 0; dp[1][1] = d[1]; for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) { if(j) dp[i + j][0] = std::max(dp[i + j][0], dp[i][j]); else dp[i + 1][0] = std::max(dp[i + 1][0], dp[i][0]); if(j != m) dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j] + d[i + 1]); } } printf("%d\n", dp[n][0]); return 0;}