决策单调性优化 dp 学习笔记

(2）：

$\begin{aligned} w(l+1,r)+w(l,r-1)\le w(l,r)+w(l+1,r-1)\qquad&(1)\\ w(l+1,r-1)+w(l,r-2)\le w(l,r-1)+w(l+1,r-2)\qquad&(2)\\ w(l+1,r)+w(l,r-1)+w(l+1,r-1)+w(l,r-2)\\ \le\\w(l,r)+w(l+1,r-1)+ w(l,r-1)+w(l+1,r-2)\\ &(1)+(2)\\ w(l+1,r)+w(l,r-2)\le w(l,r)+w(l+1,r-2) \end{aligned}$

(5).1：不会证，感性理解一下：

• 满足区间包含单调性：更长的区间 $w(l,r)$ 更大；
• 下凸函数：更大的 $w(l,r)$ 增长得更快；
• 原本就满足四边形不等式：相交总和更小；

先证明第二个：

解释：若出现上面的情况，则可以交换变成下面的情况，$f_i+f_{j}$ 变小，与 $f_i$ 和 $f_j$ 均为最小值相悖。

第一个只不过是把黑色部分去掉了。

void dfs(int opt[],int(*calw)(int,int),int l,int r,int kl,int kr)
{
	if(l>r) return;
	int mid=l+r>>1,k=kl;
	for(int i=kl;i<=kr&&i<=mid;i++)
	{
		if(calw(i,mid)<calw(k,mid)) k=i;
	}
	opt[mid]=k;
	dfs(opt,calw,l,mid-1,kl,k);
	dfs(opt,calw,mid+1,r,k,kr);
}

考虑拆成两半求解，先求满足 $[1,i]$ 的 $p$，再求满足 $[i,n]$ 的 $p$，取 $\max$。

设 $f_i$ 为前一半的 $p$，有：

$\begin{aligned} f_i&=\max\limits_{j<i}\{a_j+\sqrt{i-j}-a_i\}\\ &=-\min\limits_{j<i}\{a_i-a_j-\sqrt{i-j}\} \end{aligned}$

由于 $w1(j,i)=-\sqrt{i-j}$ 和 $w2(j,i)=a_i-a_j$ 都满足四边形不等式，所以 $w(j,i)=w1(j,i)+w2(j,i)$ 也满足四边形不等式。

那么直接分治优化转移即可，时间复杂度 $O(n\log n)$。

记得寻找 $\text{opt}(i)$ 时代价不能上取整，要最后再上取整。

参考代码

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long double db;

const int S=500005;

int n,a[S];
int opt1[S],opt2[S];
int ans[S];

inline db calw(int l,int r)
{
	return a[r]-a[l]-sqrt((db)(r-l));
}

void dfs(int opt[],db(*calw)(int,int),int l,int r,int kl,int kr)
{
	if(l>r) return;
	int mid=l+r>>1,k=kl;
	for(int i=kl;i<=kr&&i<=mid;i++)
	{
		if(calw(i,mid)<calw(k,mid)) k=i;
	}
	opt[mid]=k;
	dfs(opt,calw,l,mid-1,kl,k);
	dfs(opt,calw,mid+1,r,k,kr);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(opt1,calw,1,n,1,n);
	for(int i=1;i<=n;i++) ans[i]=ceil(-calw(opt1[i],i));
	for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
	dfs(opt2,calw,1,n,1,n);
	for(int i=1;i<=n;i++) ans[n-i+1]=max(ans[n-i+1],(int)ceil(-calw(opt2[i],i)));
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

lb[0]=1,rb[0]=n;
hed=1,til=0;
que[++til]=0;
f[0]=0;
for(int i=1;i<=n;i++)
{
	while(rb[que[hed]]<i) hed++;
	int opti=que[hed];
	f[i]=f[opti]+calw(opti+1,i);
	if(rb[opti]==i) hed++;
	else lb[opti]=i+1;
	while(hed<=til&&
		f[i]+calw(i+1,lb[que[til]])
					<
		f[que[til]]+calw(que[til]+1,lb[que[til]])
	) til--;
	if(hed>til)
	{
		if(i<n)
		{
			lb[i]=i+1,rb[i]=n;
			que[++til]=i;
		}
	}
	else
	{
		int j=que[til];
		int l=lb[j],r=rb[j],p=lb[j];
		while(l<=r)
		{
			int mid=l+r>>1;
			if(f[j]+calw(j+1,mid)<f[i]+calw(i+1,mid)) p=mid,l=mid+1;
			else r=mid-1;
		}
		rb[j]=p;
		if(p<n)
		{
			lb[i]=p+1,rb[i]=n;
			que[++til]=i;
		}
	}
}

设 $f_i$ 表示 $[1,i]$ 的代价，那么有转移：

$f_i=\min\limits_{0\le j<i}\{f_j+w(j+1,i)\}$

其中 $w(l,r)=(r-l+\sum\limits_{l\le k\le r}C_k-L)^2$。

设 $S_i=\sum\limits_{1\le j\le i}C_j$，那么 $w(l,r)=(r-l+S_r-S_{l-1}-L)^2$。

显然 $r-l+S_r-S_{l-1}-L$ 满足区间包含单调性和四边形不等式，由于 $f(x)=x^2$ 是下凸函数，所以 $w(l,r)$ 满足四边形不等式。

那么直接二分队列优化转移即可，时间复杂度 $O(n\log n)$。

参考代码

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=50005;

int n,L;
ll a[S];
int lb[S],rb[S];
int hed,til,que[S];
ll f[S];

inline ll calw(int l,int r)
{
	ll x=r-l+a[r]-a[l-1];
	return (x-L)*(x-L);
}

int main()
{
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
	lb[0]=1,rb[0]=n;
	hed=1,til=0;
	que[++til]=0;
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		while(rb[que[hed]]<i) hed++;
		int opti=que[hed];
		f[i]=f[opti]+calw(opti+1,i);
		if(rb[opti]==i) hed++;
		else lb[opti]=i+1;
		while(hed<=til&&
			f[i]+calw(i+1,lb[que[til]])
						<
			f[que[til]]+calw(que[til]+1,lb[que[til]])
		) til--;
		if(hed>til)
		{
			if(i<n)
			{
				lb[i]=i+1,rb[i]=n;
				que[++til]=i;
			}
		}
		else
		{
			int j=que[til];
			int l=lb[j],r=rb[j],p=lb[j];
			while(l<=r)
			{
				int mid=l+r>>1;
				if(f[j]+calw(j+1,mid)<f[i]+calw(i+1,mid)) p=mid,l=mid+1;
				else r=mid-1;
			}
			rb[j]=p;
			if(p<n)
			{
				lb[i]=p+1,rb[i]=n;
				que[++til]=i;
			}
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}

$\text{opt}(i,k)\le \text{opt}(i+1,k)$ 套用 1D/1D 的区间划分形 dp 的证明方法即可，仅需证明 $\text{opt}(i,k-1)\le \text{opt}(i,k)$。

不会证，感性理解一下。

四边形不等式和区间包含单调性的证明：

• 四边形不等式：

  考虑归纳，$l\ge r-2$ 时显然成立。

  仅需证明 $f_{l,r-1}+f_{l+1,r}\le f_{l,r}+f_{l+1,r-1}$。

  不妨设 $\text{opt}(l,r)=k$。

  • $k=l$ 或 $k=r-1$：

    这里假设 $k=r-1$，另一种情况同理。

    有：

    $\begin{aligned} f_{l,r}+f_{l+1,r-1}&=f_{l,k}+f_{k+1,r}+w(l,r)+f_{l+1,r-1}\\ &=f_{l,r-1}+f_{r,r}+w(l,r)+f_{l+1,r-1}\\ \end{aligned}$

    由于 $w(l,r)$ 满足区间包含单调性，所以 $w(l,r-1)\le w(l,r)$，那么有：

    $\begin{aligned} f_{l,r}+f_{l+1,r-1}&\ge f_{l,r-1}+f_{r,r}+w(l,r-1)+f_{l+1,r-1}\\ &\ge f_{l,r-1}+f_{l+1,r}\\ \end{aligned}$

    最后一步是根据 dp 转移式得到的。

  • $l<k<r-1$：

    此时设 $\text{opt}(l+1,r-1)=p$，不妨假设 $k\le p$，$k>p$ 同理：

    $\begin{aligned} f_{l,r}+f_{l+1,r-1}&=f_{l,k}+f_{k+1,r}+w(l,r)+f_{l+1,p}+f_{p+1,r-1}+w(l+1,r-1)\\ &\ge f_{k+1,r-1}+f_{p+1,r}+f_{l,k}+f_{l+1,p}+w(l,r)+w(l+1,r-1)\\ &\ge f_{k+1,r-1}+f_{p+1,r}+f_{l,k}+f_{l+1,p}+w(l,r-1)+w(l+1,r)\\ &\ge f_{l,r-1}+f_{l+1,r} \end{aligned}$

    其中：

    • 第二个不等式是因为根据归纳假设，有 $f_{k+1,r-1}+f_{p+1,r}\le f_{k+1,r}+f_{p+1,r-1}$；
    • 第三个不等式是因为 $w(l,r)$ 满足四边形不等式；
    • 第四个不等式是根据 dp 转移式得到的；

• 区间包含单调性：

  证明起来比较简单，依旧考虑归纳，$l=r$ 时显然成立。

  仅需证明 $f_{l,r-1}\le f_{l,r}$ 和 $f_{l+1,r}\le f_{l,r}$。

  这里证明 $f_{l,r-1}\le f_{l,r}$，另一个的证明是一样的。

  设 $\text{opt}(l,r)=k$。

  • $l\le k<r-1$：

    有：

    $\begin{aligned} f_{l,r}&=f_{l,k}+f_{k+1,r}+w(l,r)\\ &\ge f_{l,k}+f_{k+1,r-1}+w(l,r-1)\\ &\ge f_{l,r-1} \end{aligned}$

    其中：

    • 第二个不等式是因为 $w(l,r)$ 满足区间包含单调性，并且根据归纳假设，有 $f_{k+1,r-1}\le f_{k,r}$；
    • 第三个不等式是根据 dp 转移式得到的；

  • $k=r-1$：

    设 $\text{opt}(l,r-1)=p$，有：

    $\begin{aligned} f_{l,r}&=f_{l,r-1}+f_{r,r}+w(l,r) \end{aligned}$

    由于 $w(l,r)$ 非负，$f_{r,r}$ 也非负，所以 $f_{l,r}\ge f_{l,r-1}$。

决策单调性的证明：

先段环为链，设 $s_{i}=\sum\limits_{j=1}^i a_j$，$f_{l,r}$ 为把 $a_{[l,r]}$ 合并为一堆的最小代价，那么有转移：

$f_{l,r}=\min\limits_{l\le k<r}\{f_{l,k}+f_{k+1,r}\}+s_{r}-s_{l-1}$

显然由于 $a_i$ 非负，所以 $w(l,r)=s_r-s_{l-1}$ 满足区间包含单调性和四边形不等式，那么 $f_{l,r}$ 满足决策单调性，所以可以直接优化到 $O(n^2)$。