目录
显示
题目链接
https://www.luogu.org/problem/P1353
题解
我们一共有以下几种决策:
- 跑 \(1\) 分钟。这时的状态转移方程为:\(f[i][j]=max(f[i-1][j-1]+d[i],f[i][j])\);
- 休息至疲劳度恢复至 \(0\) 为止。状态转移方程为:\(f[i][0]=max(f[i][0],f[i-j][j])\)(即从第 \(i-j\) 分钟开始休息 \(j\) 分钟);
- 在疲劳度仍为 \(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; }