題目描述

The cows are trying to become better athletes, so Bessie is running on a track for exactly N (1 ≤ N ≤ 10,000) minutes. During each minute, she can choose to either run or rest for the whole minute.

The ultimate distance Bessie runs, though, depends on her ‘exhaustion factor’, which starts at 0. When she chooses to run in minute i, she will run exactly a distance of Di (1 ≤ Di ≤ 1,000) and her exhaustion factor will increase by 1 – but must never be allowed to exceed M (1 ≤ M ≤ 500). If she chooses to rest, her exhaustion factor will decrease by 1 for each minute she rests. She cannot commence running again until her exhaustion factor reaches 0. At that point, she can choose to run or rest.

At the end of the N minute workout, Bessie’s exaustion factor must be exactly 0, or she will not have enough energy left for the rest of the day.

Find the maximal distance Bessie can run.

奶牛們打算通過鍛煉來培養自己的運動細胞，作為其中的一員，貝茜選擇的運動方式是每天進行N(1 <= N <= 10,000)分鐘的晨跑。在每分鐘的開始，貝茜會選擇下一分鐘是用來跑步還是休息。

貝茜的體力限制了她跑步的距離。更具體地，如果貝茜選擇在第i分鐘內跑步，她可以在這一分鐘內跑D_i(1 <= D_i <= 1,000)米，并且她的疲勞度會增加1。不過，無論何時貝茜的疲勞度都不能超過M(1 <= M <= 500)。如果貝茜選擇休息，那么她的疲勞度就會每分鐘減少1，但她必須休息到疲勞度恢復到0為止。在疲勞度為0時休息的話，疲勞度不會再變動。晨跑開始時，貝茜的疲勞度為0。

還有，在N分鐘的鍛煉結束時，貝茜的疲勞度也必須恢復到0，否則她將沒有足夠的精力來對付這一整天中剩下的事情。

請你計算一下，貝茜最多能跑多少米。

輸入輸出格式

輸入格式：
第1行: 2個用空格隔開的整數：N 和 M

第2..N+1行: 第i+1為1個整數：D_i

輸出格式：
輸出1個整數，表示在滿足所有限制條件的情況下，貝茜能跑的最大距離

輸入輸出樣例

輸入樣例#1：
5 2
5
3
4
2
10
輸出樣例#1：
9
說明

【樣例說明】

貝茜在第1分鐘內選擇跑步（跑了5米），在第2分鐘內休息，在第3分鐘內跑步（跑了4米），剩余的時間都用來休息。因為在晨跑結束時貝茜的疲勞度必須為0，所以她不能在第5分鐘內選擇跑步。
.
.
.
.
.
.
.
.

分析

用dp[i,j]表示第i分鐘，疲勞度為j的最大跑步距離

枚舉時間i（從1到n）
1、dp[i,0]:=dp[i-1,0] (賦初值)
2、枚舉時間j(從1到m)看看休息了段時間的情況
如果i>=j,那么dp[i,0]:=max(dp[i,0],dp[i-j,j])
然后dp[i,j]:=max(dp[i,j],dp[i-1,j-1]+a[i]);
最后輸出是n分鐘，疲勞度為0的情況，即dp[n,0]
.
.
.
.
.
.
.

程序：

uses math; var n,m,i,j:longint; a:array[0..100000] of longint; f:Array[0..10000,0..500] of longint; beginreadln(n,m);for i:=1 to n doreadln(a[i]);for i:=1 to n dobeginf[i,0]:=f[i-1,0];for j:=1 to m dobeginif i>=j then f[i,0]:=max(f[i,0],f[i-j,j]);f[i,j]:=max(f[i,j],f[i-1,j-1]+a[i]);end;end;writeln(f[n,0]); end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9499977.html

總結

以上是生活随笔為你收集整理的[USACO08JAN]跑步Running的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。