P4552 [Poetize6] IncDec Sequence 题解

link T1 desu

我去我怎么连这么简单的差分都没有想到（）

显然差分之后就变成了选取一正一负两个数抵消。这里只考虑 $2\sim n$ 的差分数组。

那么令正数的和为 $up$，负数的和的相反数为 $lo$，那么操作次数即为 $\max(up,lo)$。

这其中的 $\min(up,lo)$ 次用于给差分数组抹平。而我们现在考虑剩下的 $|up-lo|$ 次。

显然现在差分数组内部只有正数或只有负数。

那么这些正数/负数有两种选择消失：

1. 选择与 $a_1$ 抵消，这样子会修改 $a_1$ 的值，也就等于多出一种结果。

2. 选择与 $a_{n+1}$ 抵消。

那么显然有 $|up-lo|+1$ 中结果了。

简单代码：

int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		b[i]=a[i]-a[i-1];
	}
	for(int i=2;i<=n;++i){
		if(b[i]<0) lo+=-b[i];
		if(b[i]>0) up+=b[i];
	}
	printf("%lld\n",max(lo,up));
	printf("%lld",abs(lo-up)+1);
    return 0;
}

唐啊我。