[洛谷 1353][USACO08JAN]跑步Running

题目链接

https://www.luogu.org/problemnew/show/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;
}

 

发表评论

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