Codeforces Round ＃276 (Div. 1) D. Kindergarten

Codeforces Round #276 (Div. 1) D. Kindergarten

题意： 在一个幼儿园里面，孩子被分成多个小组，每个小组必须是连续一段的，每个小组有一个魅力值，其值为该组中最大值与最小值的差，即一个人一组的小组魅力值为 $0$ 。问如何分组可以使得所有组的魅力值之和最大？

思路： 首先有一个结论，值单调上升或者单调下降的分为一组一定是最优的。那么我么需要研究的部分即为拐点处的值应该属于上一组还是下一组？我们采用 $dp$ 的做法，取最优值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int,int>PII;
const int N = 1e6+10;
int dp[N];
int a[N];
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int last=1;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++){
    
        int x1=dp[last-1]+abs(a[i]-a[last]);
        int x2=dp[last]+abs(a[i]-a[last+1]);
        dp[i]=max(x1,x2);
        if(i<n&&(a[i]-a[i-1])*(a[i+1]-a[i])<=0){
    
            last=i;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}