时间限制: 1000 ms 空间限制: 131072 KB

题目描述

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

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

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

输入

第一行：一个整数 P

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

输出

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

样例输入

样例输出

数据范围限制

提示

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int p,a[150001],f[150001][2];
    cin>>p;
    for(int i=1;i<=p;i++)
        cin>>a[i];
    f[1][0]=a[1];
    for(int i=1;i<=p;i++)
            {
                f[i][0]=max(f[i-1][1]+a[i],f[i-1][0]);
                f[i][1]=max(f[i-1][0]-a[i],f[i-1][1]);
        }
    cout<<f[p][0];
}