Codeforces 484(#276 Div 1) D Kindergarten DP

题意：给你一个数组，让你把连续的数分为一组，每一组的值为这一组数中的极差，问你这个怎样分组才能使得数组的极差和最大

解题思路：

可以分成 4种情况讨论

dp[i]  表示前 i+1项能得到的最大值

         状态                                       状态转移方程

a[i-1] < a[i]  < a[i+1]        dp[i] = dp[i-1] + a[i+1] - a[i]

a[i-1] > a[i]  < a[i+1]        dp[i] = max(dp[i-1],dp[i-2] + a[i+1] -a[i])

a[i-1] > a[i]  > a[i+1]        dp[i] = dp[i-1] - a[i+1] + a[i]

a[i-1] < a[i]  > a[i+1]        dp[i] = max(dp[i-1],dp[i-2] - a[i+1] +a[i])

 dp[n-1] 就是我们所求 

解题代码：

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=1000010;

ll dp[maxn];
int a[maxn];

int main()
{
   int n;scanf("%d",&n);
   for (int i=1;i<=n;i++) scanf("%d",&a[i]);
   dp[0]=0;
   for (int i=1;i<n;i++)
      if (a[i+1]>=a[i])
      {
         if ((i==1)||(a[i]>=a[i-1])) dp[i]=dp[i-1]+a[i+1]-a[i]; else dp[i]=max(dp[i-1],dp[i-2]+a[i+1]-a[i]);
      }
      else
      {
         if ((i==1)||(a[i]<a[i-1])) dp[i]=dp[i-1]-a[i+1]+a[i]; else dp[i]=max(dp[i-1],dp[i-2]-a[i+1]+a[i]);
      }
   cout<<dp[n-1]<<endl;
   return 0;
}

from  SanSiroWaltz

经过学弟提醒 发现一种更神的做法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ans, cx, cy, n,x;
int main() {
    ios::sync_with_stdio (0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
              cin>>x;
        if (!i || ans - x > cx) cx = ans - x;
        if (!i || ans + x > cy) cy = ans + x;
        ans = max (ans, cx + x);
        ans = max (ans, cy - x);
    }
    cout << ans;
    return 0;
}