【noip模拟赛2】牛跳

　　

描述

John的奶牛们计划要跳到月亮上去。它们请魔法师配制了P(1 <= P <=150,000)种药水，这些药水必需安原来的先后次序使用，但中间可以跳过一些药水不吃。每种药水有一个“强度”值 s ( 1 <= s <= 500 )，表示可以增强牛的跳跃能力。然而，药力的作用却是交替相反方向起作用，也就是说：当第奇数次吃药时，牛获得跳的更高的能力，而第偶数吃药时，却降低了跳高能力。在吃药前，牛的跳高能力当然为 0 。

每种药只能吃一次，开始时为第1次吃药。

请求出牛可能跳到的最高高度－－最大跳跃能力。

输入

第一行：一个整数P

下面P行：每行一个整数，表示按先后次序要吃的药水的“强度”。

输出

只一个整数，表示最大弹跳能力。

输入样例 1

8

7

2

1

8

4

3

5

6

输出样例 1

17

提示

去掉第2、4两种药水，吃药为：7,1,8,3,6；最终能力为：7-1+8-3+6=17

很明显是一个dp

主要有两个状态 第一个是当前取到第几个物品了   第二个是 现在取是加还是减

定义 1为现在取为加

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<queue>

using namespace std;

//input

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m);

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s)

#define LL long long

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

#define N 150000

int dp[N][];

int a[N];

int main()

{

   CLR(dp,);

   int n;

   RI(n);

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

    RI(a[i]);

    dp[][]=a[];

    dp[][]=;

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

    {

        //选

        dp[i][]=dp[i-][]+a[i];

        dp[i][]=dp[i-][]-a[i];

        dp[i][]=max(dp[i][],dp[i-][]);

        dp[i][]=max(dp[i][],dp[i-][]);

    }

    cout<<max(dp[n][],dp[n][]);

}