Luogu P4552 [Poetize6] IncDec Sequence 更好的題解

原題鏈接

第一步對於學過差分的人應該不難想
定義差分數組 $dis \quad s.t. \quad dis[i] = a[i] - a[i-1] $
那麼不難發現問題一隻要讓 \(dis[2] ... dis[n]\)中全部為 \(0\) 即可
區間\([l,r]\)加一操作在差分數組中意味著\(dis[l]=dis[l]+1,dis[r+1]=dis[r+1]-1\)
即在差分數組中每次選取\((x,y),dis[x]=dis[x]+1,dis[y]=dis[y]-1\)
註意這裡\(x,y\)可以選取\(1...n+1\)
減一同理
最後要使\(dis[2] ... dis[n]\)全為0,首先在\(dis[2] ... dis[n]\)選取一個正數和一個負數是他們配對加一或減一,直到最後只剩下一個數,不難發現這個數就是\(dis[2] ... dis[n]\)中正數的和\(sum^+\)和負數的和的絕對值\(|sum^-|\)的差,讓他與dis[1]或dis[n+1]配對即可

最後整理可得:\(min(sum^+,sum^-)+|sum^+-|sum^-||\),即\(max(sum^+,|sum^-|)\)就是第一小問答案

對於第二小問,不難註意答案序列的不同只和在第一小問中最後剩下的那個數\(k = sum^+-|sum^-|+1\)有關
我們這裡不妨設\(k > 0\),那麼它可以和1或n+1配對,這裡兩個操作就代表了原數組\(a[1,k-1]\)全部加一和原數組\(a[k,n]\)全部減一,也就產生了兩種不同的序列
那麼這兩種操作進行的次數的和必然是\(k\),那麼就產生了k+1中不同的選法(第一個操作進行\(0...k\)次)
對於\(k < 0\)的情況可以同樣地進行討論
那麼第二問答案就是\(k+1=|sum^+-|sum^-||+1\)

//c++AC代碼
#include <bits/stdc++.h>
using namespace std;

int n,a[(int)1e5+5],dis[(int)1e5+5];
long long sum_z,sum_f,rest;

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)
	{
		scanf("%d",a+i);
	}
	for(int i = 1;i <= n;++i)
	{
		dis[i]=a[i]-a[i-1];
	}
	for(int i = 2;i <= n;++i)
	{
		if(dis[i] > 0)
			sum_z+=dis[i];
		else 
			sum_f+=dis[i];
	}
	rest=sum_z+sum_f;
	printf("%lld\n",max(sum_z,std::abs(sum_f)));
	printf("%lld",(long long)std::abs(sum_z-std::abs(sum_f))+1);
	return 0;
}