一、题意分析​

本题中，Farmer John 的奶牛想借助药水实现跳跃，药水有严格的服用顺序，服用时间步的奇偶性会影响跳跃能力的增减。需要在给定的 P 种药水及对应强度下，通过合理选择服用药水的顺序，使得奶牛最终的跳跃能力达到最大值。其中，每种药水只能服用一次，且一旦开始服用，每个时间步都必须有药水服用（可跳过部分药水） ，初始跳跃能力为 0，药水强度范围在 1 到 500 之间，药水数量 P 的范围是 1 到 150,000。​

二、解题思路​

本题可以使用动态规划的方法来解决。动态规划的核心在于通过记录子问题的解，避免重复计算，从而高效地得到最终问题的答案。​

定义状态：设dp[i][0]表示在第i个时间步（奇数时间步）服用第i种药水后能达到的最大跳跃能力，dp[i][1]表示在第i个时间步（偶数时间步）服用第i种药水后能达到的最大跳跃能力。这里的时间步从 1 开始计数。​

状态转移方程​

对于奇数时间步i（即i % 2 == 1），此时服用第i种药水会增加跳跃能力，状态转移方程为：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + strength[i]。这表示当前奇数时间步服用第i种药水的最大跳跃能力，是前一个时间步（无论是奇数时间步dp[i - 1][0]还是偶数时间步dp[i - 1][1]）能达到的最大跳跃能力加上当前药水的强度strength[i]。​

对于偶数时间步i（即i % 2 == 0），此时服用第i种药水会减少跳跃能力，状态转移方程为：dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) - strength[i]。意味着当前偶数时间步服用第i种药水的最大跳跃能力，是前一个时间步（奇数时间步dp[i - 1][0]或偶数时间步dp[i - 1][1]）能达到的最大跳跃能力减去当前药水的强度strength[i]。​

初始化：在开始服用药水前，跳跃能力为 0，即dp[0][0] = dp[0][1] = 0 ，表示还未开始服用药水时的状态。​

最终答案：遍历完所有的药水后，最终的最大跳跃能力值就是dp[P - 1][0]和dp[P - 1][1]中的较大值，因为最后一个时间步无论是奇数还是偶数，都可能是最大跳跃能力出现的情况。

代码

#include <iostream>
#include <cstdio>   // 添加这一行以使用 scanf 和 printf
#include <climits>  // 添加这一行以使用 INT_MAX
using namespace std;

int n;
int v[150000];
int f[150000][2];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&v[i]);
    f[0][0]=v[0]; f[0][1]=0;
    for(int i=1;i<n;i++){
        int j=f[i-1][1],mins=INT_MAX;
        for(;j<i;j++) if(v[j]<mins) mins=v[j];
        if(mins<v[i]){
            f[i][0]= f[i-1][0]+v[i]-mins;
            f[i][1]=i;
        }
        else{
            f[i][0]=f[i-1][0];
            f[i][1]=f[i-1][1];     
        }        
    }
    printf("%d\n",f[n-1][0]);
    system("pause");
    return 0;
}
```

```