POJ3661Running題解動态規劃DP

Running

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 3129	Accepted: 1073

Description

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
      

Source

USACO 2008 January Silver     狀态： d[i][j]表示前i分疲勞值為j時最大值   狀态轉移方程： d[i][j]=d[i-1][j-1]+a[i]      d[i][0]=max{d[i-j][j]} j<=m&&j<i     代碼：   #include<cstdio>

#define max(a,b) ((a)>(b)?(a):(b))

int a,d[100005][505],n,m,i,j;

int main()

{

scanf("%d%d",&n,&m);

for(i=1;i<=n;i++)

{

scanf("%d",&a);

d[i][0]=d[i-1][0];

for(j=1;j<=m;j++)

{

if(j<i)d[i][0]=max(d[i][0],d[i-j][j]);//前j分開始休息

d[i][j]=d[i-1][j-1]+a;//繼續跑

}

}

printf("%d/n",d[n][0]);

}

附官方題解 USACO JAN08 Problem 'cowrun' Analysis

by Neal Wu

This is a straightforward dynamic programming (DP) problem. To solve the problem, we want to find, for each k such that 0 <= k <= N, the maximum possible distance Bessie could have run after the first k minutes, if she has a rest factor of 0. (For example, if we can obtain a distance of 14 after 5 minutes with a rest factor of 0, or we can obtain a distance of 15 after 5 minutes with a rest factor of 0, we would always choose the second over the first.) Clearly, the best such value for 0 is 0. Then, for each minute i of the N minutes, we can compute all of the next values possible with the following method:

-First, try to not run during the minute, and see if this produces an improvement. (Thus, check if the best value for i is better than the one for i + 1.)

-Then, for each number k from 1 to M, let Bessie run for exactly k minutes and then rest for k minutes. See if this new value produces a greater value than the best value for i + 2k (which is the number of minutes finished after running for k minutes and resting for another k minutes).

Thus, since we do M updates for each of the N minutes, our total complexity is O(NM). The following is a sample solution:

#include<cstdio>

int N,M,i,j,dist[10005],best[10005];

int main ()

{

scanf("%d%d",&N,&M);

for(i=0;i<N;i++)

scanf("%d",dist+i);

for(i=0;i<N;i++)

{

if(best[i]>best[i+1])

best[i+1]=best[i];

int sum=best[i],pos=i;

for(j=0;j<M&&pos<N;j++)

{

sum+=dist[i+j];

pos+=2;

if(sum>best[pos])

best[pos]=sum;

}

}

printf("%d/n",best[N]);

}