usaco 월간 2008 January Best Cow Line Bey의 아침 운동 계획 문제풀이

런닝 문제 풀이
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 4954
 
Accepted: 1835
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 ofDi (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
중국어 뜻: 젖소들은 운동을 통해 자신의 운동 세포를 배양할 계획이다. 그 중 하나로서 베시가 선택한 운동 방식은 매일 N(1<=N<=10000)분의 조깅을 하는 것이다.베시는 매 분의 시작에 다음 분을 달리기로 할지 휴식으로 할지 선택한다.베시의 체력이 그녀가 달리는 거리를 제한했다.더욱 구체적으로 만약에 베시가 i분 안에 달리기를 선택한다면 그녀는 이 분 안에 D 를 뛸 수 있다i(1<=D i <=1000)미터, 그리고 그녀의 피로도는 1 증가합니다.하지만 베시의 피로도는 언제나 M(1 < = M < = 500)을 넘으면 안 된다.만약 베시가 휴식을 선택한다면, 그녀의 피로도는 분당 1씩 줄어들지만, 그녀는 피로도가 0까지 회복될 때까지 쉬어야 한다.피로도가 0일 때 쉬면 피로도는 더 이상 변하지 않는다.조깅이 시작되었을 때, 베시의 피로도는 0이었다.그리고 N분의 운동이 끝날 때, 베시의 피로도도 0으로 회복해야 한다. 그렇지 않으면, 그녀는 하루 종일 남은 일에 대처할 충분한 정력이 없을 것이다.베시가 최대 몇 미터를 뛸 수 있는지 계산해 보세요.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
욕심이라고 표시했지만 DP로 쓰려고요.
첫 번째는 필득을 지향하고 직접 방정식을 추측한다.

for (i=1;i<=n;i++)
{
  f[i][0]=f[i-1][1];
  for (j=1;j<=m;j++)
    f[i][j]=max(f[i-1][j+1],f[i-1][j-1]+a[i]);
}

그 중에서 f[i][j]는 i초까지 피로도가 j일 때 가장 먼 거리를 나타낸다.
그리고 샘플을 한 번 훑어보고 ~~~~~~WA를 제출합니다!
제목을 자세히 살펴보자: 매번 쉴 때마다 0까지 쉬어야 한다!이거 어떡하지?
SYC 황소 지적: 이 오류를 방지하기 위해서는 순차적으로 밀어야 합니다!
그래서 코드를 끙끙거리며 썼다.

for (i=1;i<=n;i++)
  {
    for (j=1;j<=min(m,n-i);j++)
    {
      f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
      f[i+j][0]=max(f[i+j][0],f[i][j]);
    }
  }

그래도 못 넘어가!마지막으로 한참을 생각했는데 나는 또 다른 상황을 고려하지 않은 것을 발견했다. i-j분에 젖소가 계속 쉰다!
그러니까 한마디만 더 하면 돼.AC 코드는 다음과 같습니다.

#include<stdio.h>
#include<iostream>
using namespace std;
int f[10001][502],a[10001],n,m,i,j,maxx,ans;
int main()
{
  scanf("%ld %ld",&n,&m);
  for (i=1;i<=n;i++)
    scanf("%ld",&a[i]);
  f[1][1]=a[1];
  for (i=1;i<n;i++)
  {
    for (j=0;j<=min(m,n-i);j++)
    {
      f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+a[i+1]);
      f[i+j][0]=max(f[i+j][0],f[i][j]);
      f[i+1][0]=max(f[i][0],f[i+1][0]);
    }
  }
  printf("%ld",f[n][0]);
  return 0;
}