Codeforces | CR #276 Div.1 – D.Kindergarten | 贪心

---

Description

给定一个数列，请你将其分为若干段。每一段的值定义为这一段数中最大值与最小值的差。请求出一种分法，使得这若干段的值的和最大。

---

Input Format

第一行一个正整数 $N$，代表数列长度。

第二行 $N$ 个整数，代表数列。

---

Output Format

一行一个正整数表示最大权值。

---

Input Sample

Sample 01

5
1 2 3 1 2

Sample 02

3
3 3 3

---

Output Sample

Sample 01

3

Sample 02

0

---

Data Range

$1 \le N \le 10^6$，$-10^9 \le a_i \le 10^9$。

---

Solution

因为求的是序列极差，若序列不是单调的，可以证明将其分为几个单调的子序列答案一定更优。故分成的子序列一定是一些单调的子序列。

考虑贪心决策将单调序列的分界点划分到前面一个序列还是后面。设 $F[i]$ 表示前 $i$ 个元素形成序列分成若干组的最大值。若 $a_{i-2} … a_i$ 是单调的，那么 $F[i] = F[i-1] + |a_i – a_{i-1}|$，否则 $F[i] = \max(F[i-1] , F[i-2] + |a_i – a_{i-1}|)$（左边是将 $F_{i-1}$ 划分到后面的序列，右边是将 $F_{i-1}$ 划分到后面的序列）。

---

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

typedef long long ll;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;

int src[1000005];

ll F[1000005];

bool Mono(int x){
    if(src[x]>=src[x-1] && src[x-1]>=src[x-2])
        return true;
    if(src[x]<=src[x-1] && src[x-1]<=src[x-2])
        return true;
    return false;
}

int main(){
    Read(N);
    rep(i,1,N)
        scanf("%d",&src[i]);
    F[1]=0;
    F[2]=abs(src[2]-src[1]);
    rep(i,3,N){
        if(Mono(i))
            F[i]=F[i-1]+abs(src[i]-src[i-1]);
        else
            F[i]=max(F[i-1],F[i-2]+abs(src[i]-src[i-1]));
    }
    printf("%lld\n",F[N]);
    return 0;
}