F - 你這是第一次讓我看到落淚了呢?POJ - 3661?

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.

Input

* Line 1: Two space-separated integers:?N?and?M
* Lines 2..N+1: Line?i+1 contains the single integer:?Di

Output

* Line 1: A single integer representing the largest distance Bessie can run while satisfying the conditions.
　

Sample Input

5 2 5 3 4 2 10

Sample Output

9

題意：N分鐘，第i分鐘能跑Di的長度；每分鐘可以選擇跑或者休息，跑+1疲勞值，休息-1疲勞，如果開始休息，必須等疲勞降低到0才開始跑；疲勞度不能超過M；?N分鐘后疲勞值必須為0；求最大路程

思路：dp[i][j]數(shù)組存第i分鐘結(jié)束時疲勞值為j的最大路程；

?????????? 剛開始是順著題意來想的：休息 dp[i][j]=dp[i-1][j+1]
????????????????????????????????????????????????????? 走 dp[i][j]=max （ dp[i-1][j-1](之前在走)，（之前在休息）dp[i-1][0]? ）+var[i]

????????? 但是這樣走的那里不知道dp[i-1][j-1]究竟是在走還是休息。就在想能不能dp[i][j]里存的都是走的狀態(tài)，然后發(fā)現(xiàn)輸出是dp[N][0]（N需要算的是停留的狀態(tài)）,就可以反過來想:走：?dp[i][j ]= dp[i-1][j-1] + var[i]?? （假設(shè)dp[i][j]里存的都是走的狀態(tài)）

???????????????????????????????????????????????????????????????????????????? 休息：dp[i][0]=max( dp[i][0], dp[i-j][j] )??? （j指前面休息了j-1分鐘）

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <set> #include <stack> #include <vector> #define fora(i,a,b) for(i=a;i<b;i++) #define fors(i,a,b) for(i=a;i>b;i--) #define fora2(i,a,b) for(i=a;i<=b;i++) #define fors2(i,a,b) for(i=a;i>=b;i--) #define PI acos(-1.0) #define eps 1e-6 #define INF 0x3f3f3f3ftypedef long long LL; typedef long long LD; using namespace std; const int maxn=10000+5; int N,M; int var[maxn]; int dp[maxn][505]; void init() {memset(dp,0,sizeof(dp)); } int main() {while(~scanf("%d%d",&N,&M)){init();int i,j;fora2(i,1,N){scanf("%d",var+i);}int ans=0;fora2(i,1,N){dp[i][0]=max(dp[i][0],max(dp[i-1][0],dp[i-1][1]));fora2(j,1,M)//選擇走{if(j>i)break;dp[i][j]=dp[i-1][j-1]+var[i];}fora2(j,1,M)//i秒休息結(jié)束,共休息了j秒{if(i-j<j)break;dp[i][0]=max(dp[i][0],dp[i-j][j]);}}printf("%d\n",dp[N][0]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/107acm/p/9428302.html

總結(jié)

以上是生活随笔為你收集整理的F - 你这是第一次让我看到落泪了呢 POJ - 3661Running 区间DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。