题目大意：
给你n个药的序列，牛从时间1开始吃药，在奇数时间吃药可以增加弹跳力，在偶数时间吃药则会减少弹跳力。在某一时间，你可以跳过一些药，但一旦吃过某种药，你就不能在选前面的药了。问你某一个吃药的序列，使牛最终的弹跳力最大。
思路：
虽然题目不难，但思考题目的过程十分有意思。对于某种药，共有4中状态：在奇数时间吃、在奇数时间不吃、在偶数时间吃以及在偶数时间不吃。关键在于这4种状态之间的转移。因为如果跳过某种药是不需要花费时间的，所以在某2次的吃药时间内，时间相当于是静止的，一直维持在第1次吃药的时间段内。
所以可用一数组max[i][2][2]表示状态，第i种药在奇/偶时间段内吃/不吃。可得状态转移可表示为：
max[i][0][0] = Max (max[i-1][0][0], max[i-1][0][1]);
max[i][0][1] = Max (max[i-1][1][0], max[i-1][1][1]) - high[i];
max[i][1][0] = Max (max[i-1][1][0], max[i-1][1][1]);
max[i][1][1] = Max (max[i-1][0][0], max[i-1][0][1]) + high[i];
代码：
#include <iostream>
using namespace std;
const int MAX = 150005;
int high[MAX];
int max[MAX][2][2];
int n;
void Input ()
{
scanf("%d", &n);
int i;
for (i=1; i<=n; i++)
scanf("%d", &high[i]);
}
int Max (int a, int b)
{
return ( a>b?a:b );
}
void Solve ()
{
int i;
for (i=1; i<=n; i++)
{
max[i][0][0] = Max (max[i-1][0][0], max[i-1][0][1]);
max[i][0][1] = Max (max[i-1][1][0], max[i-1][1][1]) - high[i];
max[i][1][0] = Max (max[i-1][1][0], max[i-1][1][1]);
max[i][1][1] = Max (max[i-1][0][0], max[i-1][0][1]) + high[i];
}
printf("%d\n", Max ( Max(max[n][0][0], max[n][0][1]), Max(max[n][1][0], max[n][1][1])) );
}
int main ()
{
Input ();
Solve ();
return 0;
}