AGC040E Prefix Suffix Addition 做题记录

你有一个长为 nn 的序列 x1,x2,,xnx_1,x_2,\dots,x_n,一开始全部为 00,你现在可以以任意顺序进行任意次以下两种操作:

  1. 选定整数 1kn1\le k\le n 与不下降非负整数序列 c1,c2,,ckc_1,c_2,\dots,c_k,对所有 1ik1\le i \le k,令 xix_i 加上 cic_i
  2. 选定整数 1kn1\le k\le n 与不上升非负整数序列 c1,c2,,ckc_1,c_2,\dots,c_k,对所有 1ik1\le i \le k,令 xnk+ix_{n-k+i} 加上 cic_i

问最少进行多少次操作使得 xi=aix_i=a_i

1n2×1051\le n\le 2\times 10^51ai1091\le a_i\le 10^9

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

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

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

考虑设 yiy_i 表示第一种操作让 xix_i 增加了多少(yn+1=an+1=y0=a0=0y_{n+1}=a_{n+1}=y_0=a_0=0),则答案为 i=1n+1[yi1>yi]+[ai1yi1<aiyi]\sum\limits_{i=1}^{n+1}[y_{i-1}>y_i]+[a_{i-1}-y_{i-1}<a_{i}-y_{i}]

dpi,jdp_{i,j} 表示确定完 y[1,i]y_{[1,i]}yi=jy_i=j 的前 ii 项的答案,不难发现对于同一个 iijj 越大 dpi,jdp_{i,j} 越小,而转移时 jj' 越小 dpi1,jdp_{i-1,j'} 转移到 dpi,jdp_{i,j} 的代价越小。注意到对于同一个 iidpi,jdp_{i,j} 最多只有三种取值,那么记录下这三种取值的值和最小的 jj 即可转移。

时间复杂度 O(n)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])