[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注