AGC040E Prefix Suffix Addition 做题记录

你有一个长为 $n$ 的序列 $x_1,x_2,\dots,x_n$，一开始全部为 $0$，你现在可以以任意顺序进行任意次以下两种操作：

1. 选定整数 $1\le k\le n$ 与不下降非负整数序列 $c_1,c_2,\dots,c_k$，对所有 $1\le i \le k$，令 $x_i$ 加上 $c_i$。
2. 选定整数 $1\le k\le n$ 与不上升非负整数序列 $c_1,c_2,\dots,c_k$，对所有 $1\le i \le k$，令 $x_{n-k+i}$ 加上 $c_i$。

问最少进行多少次操作使得 $x_i=a_i$。

$1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。

对于这种和单调性有关的情况，一般考虑差分序列。那么设 $b_i=x_{i+1}-x_i$。

考虑只有一种操作怎么做，显然两种操作是对称的，所以只用考虑第一种操作。不难发现第一种操作相当于把 $b_{[1,k-1]}$ 都加上任意非负整数， 把 $b_k$ 减去任意非负整数。而我们的目的是让 $b_i=a_{i+1}-a_i$，所以答案即为 $\sum\limits_{i=1}^{n-1}[a_i>a_{i+1}]+1$。

同理，只有第二种操作时的答案为 $\sum\limits_{i=1}^{n-1} [a_i<a_{i+1}]+1$。

考虑设 $y_i$ 表示第一种操作让 $x_i$ 增加了多少（$y_{n+1}=a_{n+1}=y_0=a_0=0$），则答案为 $\sum\limits_{i=1}^{n+1}[y_{i-1}>y_i]+[a_{i-1}-y_{i-1}<a_{i}-y_{i}]$。

设 $dp_{i,j}$ 表示确定完 $y_{[1,i]}$ 且 $y_i=j$ 的前 $i$ 项的答案，不难发现对于同一个 $i$，$j$ 越大 $dp_{i,j}$ 越小，而转移时 $j'$ 越小 $dp_{i-1,j'}$ 转移到 $dp_{i,j}$ 的代价越小。注意到对于同一个 $i$，$dp_{i,j}$ 最多只有三种取值，那么记录下这三种取值的值和最小的 $j$ 即可转移。

时间复杂度 $O(n)$，代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=200005,inf=1e9;

int n,a[S];
int f[S][3],g[S][3];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	a[0]=a[n+1]=0;
	f[0][0]=0,g[0][0]=0;
	f[0][1]=g[0][1]=inf;
	f[0][2]=g[0][2]=inf;
	for(int i=1;i<=n+1;i++)
	{
		int y[7],dp[7]={inf,inf,inf,inf,inf,inf,inf};
		for(int j=0;j<3;j++) y[j]=a[i]-a[i-1]+f[i-1][j];
		for(int j=3;j<6;j++) y[j]=f[i-1][j-3];
		y[6]=0;
		for(int j=0;j<7;j++)
		{
			int v=y[j];
			if(v<0||v>a[i]) continue;
			for(int k=0;k<3;k++)
			{
				int u=f[i-1][k];
				if(u<0||u>a[i-1]) continue;
				dp[j]=min(dp[j],g[i-1][k]+(u>v)+(a[i-1]-u<a[i]-v));
			}
		}
		int id[7]={0,1,2,3,4,5,6};
		sort(id,id+7,[&](int a,int b){return dp[a]<dp[b]||(dp[a]==dp[b]&&y[a]<y[b]);});
		int p=0;
		for(int j=0;j<7&&p<3;j++)
		{
			int k=id[j];
			if(p==0||dp[k]!=g[i][p-1])
			{
				f[i][p]=y[k],g[i][p]=dp[k];
				p++;
			}
		}
		for(int j=p;j<3;j++) f[i][j]=g[i][j]=inf;
	}
	printf("%d\n",g[n+1][0]);
	return 0;
}
// (y[i]>y[i+1])+(a[i]-y[i]<a[i+1]-y[i+1])