增减序列

AcWing-100-增减序列

分析

见《进阶指南》第23页。

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 100010;
LL a[N];

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);

    LL pos = 0, neg = 0;
    for (int i = 2; i <= n; ++ i) {
        LL d = a[i] - a[i - 1];
        if (d > 0)
            pos += abs(d);
        else
            neg += abs(d);
    }
    printf("%lld\n", min(pos, neg) + abs(pos - neg));
    printf("%lld\n", abs(pos - neg) + 1);
    return 0;
}