Running
| Time Limit: 1000MS |
Memory Limit: 65536K |
| Total Submissions: 7477 |
Accepted: 2810 |
Description
The cows are trying to become better athletes, so Bessie isrunning 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 adistance of Di (1 ≤ Di ≤ 1,000) and her exhaustion factorwill increase by 1 -- but must never be allowed to exceed M (1 ≤ M ≤ 500). If she chooses to rest, herexhaustion factor will decrease by 1 for each minute she rests. She cannotcommence 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 exaustionfactor must be exactly 0, or she will not have enough energy left for the restof 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+1contains the single integer: Di
Output
* Line 1: A single integer representing the largest distanceBessie can run while satisfying the conditions.
SampleInput
5 2534210SampleOutput
9Source
USACO 2008 January Silver
算法分析：
题意：
一个牛跑步，总花费n分钟，第i分钟如果这个人在跑步（没有休息）那么他跑的距离为Di，同时他的疲劳值会加1（第0分钟时疲劳值为0），疲劳值不能超过m，如果这个人第i分钟选择休息，那么每休息一分钟疲劳值便减少1，但是，一旦选择休息，要休息到疲劳值为0才会继续行动。n分钟过后，这个人的疲劳值必须为0，问n分钟最多能跑多少米
分析：区间dp，我们设dp[i][j]为i分钟之后疲劳值为j能跑的最远距离，接下来就是关键的状态转移方程了。
第一种，当j！=0时，由题意得，i分钟之内一定在跑步，方程：
dp[i][j]=dp[i-1][j-1]+d[i];
第二种：当j==0时，
1.可以选择这一分钟之内什么都不干，dp[i][0]=dp[i-1][0];
2.如果它是由某一时刻休息得来的，假设这一个叉的时间段为k，则dp[i][0]=max(dp[i][0],dp[i-k][k])代码实现：
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define M 505
#define N 10010
int d[N],dp[N][M];
int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){scanf("%d",&d[i]);}memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j-1]+d[i];}dp[i][0]=dp[i-1][0];for(int k=1;k<=m&&i>=k;k++){dp[i][0]=max(dp[i][0],dp[i-k][k]);}}printf("%d\n",dp[n][0]);}return 0;
}