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

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

题意： in a kindergarten,Children are divided into groups,Each group must be a continuous segment,Each group has a Charisma score,Its value is the difference between the largest value and the smallest value in the group,That is, the group attractiveness value of a group of people $0$ .Ask how to group so that the sum of all groups' charisma can be maximized？

思路： 首先有一个结论,It must be optimal to group the values ​​monotonically increasing or monotonically decreasing.Then the part we need to study is whether the value at the inflection point belongs to the previous group or the next group？我们采用 $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;
}