H牛跳【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

提示

来源：
来自 <http://www.dingbacode.com/contest/19/problem/H>

题解：
dp记录偶数布和奇数布的最优情况

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

int a[150010][5];
int b[150010];
int main()
{
    int N;
    cin>>N;
    for (int i =1;i<=N;i++)
        cin>>b[i];
    a[1][1]=b[1];
    a[1][2]=0;
    for (int i=2;i<=N;i++)
    {
        a[i][1]=max(a[i-1][2]+b[i],a[i-1][1]);
        a[i][2]=max(a[i-1][1]-b[i],a[i-1][2]);
    }
    cout<<a[N][1]<<endl;
    return 0;
}