POJ 2181 Jumping Cows

n개의 약 서열을 드리겠습니다. 소는 시간 1부터 약을 먹습니다. 홀수 시간에 약을 먹으면 점프력을 증가시킬 수 있고, 짝수 시간에 약을 먹으면 점프력을 감소시킬 수 있습니다.어느 순간에는 약을 건너뛸 수 있지만, 일단 어떤 약을 먹으면 앞의 약을 고를 수 없다.어떤 약을 먹는 서열을 물어보면 소의 최종 점프력이 가장 크다.
해법은 여러 가지가 있는데 dp도 되고 욕심도 낼 수 있다.
동적 계획:
dp[i][0]는 i번째 약을 받았을 때 기수 개의 약의 최대 점프력을 받았다고 밝혔다.
dp[i][1]은 i번째 약을 받았을 때 짝수 약의 최대 점프력을 얻었다는 뜻이다.
방정식은 바로,
       dp[i][0] = max(dp[i-1][0], dp[i-1][1]- v[i]);        dp[i][1] = max(dp[i-1][1], dp[i-1][0]+v[i]);
욕심 해법:
원 서열을 몇 개의 소절로 나누어 각 소절의 최대치가 최소치 앞에 있는 것을 확보하고, 매번 약을 먹을 때마다 최대치를 먼저 먹고, 최소치를 먹으면 점프력이 끊임없이 증가하는 것을 보장할 수 있다.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[151000][2];
int maxd(int a,int b)
{
    return a<b?b:a;
}
int main()
{
    int n,i,t;
    while (scanf("%d",&n) != EOF)
    {
        dp[0][0]=0;
        dp[0][1]=0;
        for (i=1; i<=n; i++)
        {
            scanf("%d",&t);
            dp[i][0]=maxd(dp[i-1][0],dp[i-1][1]-t);
            dp[i][1]=maxd(dp[i-1][1],dp[i-1][0]+t);
        }
        printf("%d
",maxd(dp[n][0],dp[n][1]));
    }
}