[洛谷 1353][USACO08JAN]跑步Running

题目链接

https://www.luogu.org/problem/P1353

题解

我们一共有以下几种决策：

1. 跑 \(1\) 分钟。这时的状态转移方程为：\(f[i][j]=max(f[i-1][j-1]+d[i],f[i][j])\)；
2. 休息至疲劳度恢复至 \(0\) 为止。状态转移方程为：\(f[i][0]=max(f[i][0],f[i-j][j])\)（即从第 \(i-j\) 分钟开始休息 \(j\) 分钟）；
3. 在疲劳度仍为 \(0\) 时继续休息 \(1\) 分钟。状态转移方程为：\(f[i][0]=max(f[i][0],f[i-1][0])\)。

#include <cstdio>
#include <algorithm>
using namespace std;
int d[10005],f[100005][505];
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
  scanf("%d",&d[i]);
 for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=min(i,m);j++)
   f[i][0]=max(f[i][0],f[i-j][j]);
  f[i][0]=max(f[i][0],f[i-1][0]);
  for(int j=1;j<=min(i,m);j++)
   f[i][j]=max(f[i-1][j-1]+d[i],f[i][j]);
 }
 printf("%d\n",f[n][0]);
 return 0;
}