$Incedec$序列

问题描述：给定一个数组$s[$ $]$，每次可以选定一个区间$(l,r)$，使这个区间内的数都$+1$或$-1$。求最少需要多少次操作才能使数列中所有数相同，及执行最少操作次数最终得到的数列可能有多少种。

记$a$为原数组，$s$为$a$数组的前缀和数组，则每次在$s$数组中一段区间$(l,r)$中的数都加$1$(减$1$)可以转化成操作$a[l]+1, a[r+1]-1$ ($a[l]-1, a[r+1]+1$)。所以要将$s[$ $]$变为全部一样即要将$a[$ $]$转变成除$a[1]$外全为$0$(这样前缀和数组才相同)。
所以问题就转化成每次选两个$a[$ $]$中的数，一个$+1$，一个$-1$，将除$a[1]$外的元素都变成$0$，明显每次找一个正数$-1$，一个负数$+1$是最优策略。因为$sum[正]$和$sum[负]$不一定刚好完全抵消，最后可能有剩余，假设最后剩余为a[x]，那么就只操作过$a[x]$和$a[1]$(只改变$a[1]$)或者对$a[x]$和$a[n+1]$(只改变$a[x]$)

如果对$a[x]$和$a[n+1]$进行$a[x]$次操作，可以得到一种序列，如果对$a[x]$和$a[n+1]$执行$a[x]-1$次操作可以得到$1$种序列，…最后执行$0$次$a[x]$和$a[n+1]$操作(全部执行$a[1]$和$a[x]$操作)，即$0$-$a[x]$种一共$a[x]+1$操作，对应$a[x]+1$种不同序列

所以最终我们可以得出结论：最少执行次数为$min(|sum[正]|, sum[负]|) + abs(|sum[正]|-sum[负]|)$，最少次数对应的序列最多有$abs(|sum[正]|-sum[负]|)+1$种

$Acwing.100$增减序列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int a[N], s[N];
int main()
{
    int n; 
    scanf("%d", &n);
    ll sum1 = 0, sum2 = 0;
    scanf("%d", &s[1]); a[1] = s[1];  // 先将s[1]读入，因为后面只记录a[2]到a[n]
    for (int i = 2; i <= n; i ++) 
    {
        scanf("%d", &s[i]);
        a[i] = s[i] - s[i - 1];
        if (a[i] > 0) sum1 += a[i];  // 记录正数和
        else sum2 += a[i];  // 记录负数和
    }
    printf("%lld\n%lld", min(sum1, -sum2) + abs(sum1 + sum2), abs(sum1 + sum2) + 1);

    return 0;
}