dp斜率优化

T1 hdu3507 打印文章

题目描述：

给定一个含 $ n $ 个数的数列 $ C_n $ 和 $ M $ ,将 $ C_n $ 分为若干段 $ [a,b] $ ,求所有子段的 $ W $ 之和的最小值.

\[W_{a,b}=(\sum^b_{i=a}C_i)^2+M \]

$ n\le 5*10^5\quad M\le 1000 $

思路：

\[\begin{align} &\quad\ 令S_i=\sum^i_{j=1}C_j\\ &\therefore W_{a,b}=S_b-S_{a-1}\\ &\quad\ 令f_i为前i项的最小W\\ &\therefore f_i=\min_{j=1}^{i-1}{(f_j+(S_i-S_j)^2)}+M\\ &\quad\ {\color{OrangeRed}{f_i}}=\min_{j=1}^{i-1}{({\color{ForestGreen}{f_j}}+{\color{OrangeRed}{S_i^2}}+{\color{ForestGreen}{S_j^2}}-{\color{RoyalBlue}{2*S_i*S_j}})+{\color{OrangeRed}{M}}}\\ \end{align} \]

将只含不确定性 $ (j) $ 的项放在左边,含有 $ i $ 的项放在右边:

\[\begin{align} &\boxed{\therefore {\color{ForestGreen}{f_j}}+{\color{ForestGreen}{S_j^2}}={\color{RoyalBlue}{(2*S_i)*S_j}}+({\color{OrangeRed}{f_i}}-{\color{OrangeRed}{S_i^2}}-{\color{OrangeRed}{M}})}\\ &\Rightarrow{\color{ForestGreen}{y}}={\color{RoyalBlue}{kx}}+{\color{OrangeRed}{b}}\\ &\boxed{\therefore y=f_j+S_j^2\quad {\color{Maroon}{k=2*S_i}}\quad x=S_j\quad {\color{Maroon}{b=f_i-S_i^2-M(目标:最小化)}}} \end{align} \]

$ \therefore\ $ 每个决策 $ j $ 都对应着一个点 $ (S_j,f_j+S_j^2) $ ,目标是使纵截距 $ b $ 最小.

维护一个下凸包:

如图所示b取最小:

**<!!!>此时满足: $ k_h( $ 线的斜率 $ )<k( $ 点的决策斜率 $ )<k_i( $ 线的斜率 $ ) $ **

利用单调队列维护决策点.

$ *\because $ 对于任意 $ j_1<j_2 $ ,必有 $ S_{j_1}<S_{j_2} $ ,故不存在 $ J $ 点所示情况,即新的决策点必出现在下突壳的最右端.

维护下突壳:检查新加入的点 $ L $ 和之前两点 $ K,E $ 是否满足下凸性,若不满足则弹出队尾 $ (K) $ ,然后将新决策点 $ (L) $ 入队.

随着 $ i $ 的增加,斜率 $ {\color{OrangeRed}{ k=2*S_i\ 单调递增}}\ $ ,故一次查询的最优决策点之前的斜率 $ \le k $ 的线均无效,出队.
队头即是最优决策点.
(若 $ k $ 不满足单调递增(如 $ T4 $ ),则不能直接弹出斜率 $ \le k $ 的所有决策点,队头也不一定是最优决策点,要在单调队列中二分出一个点 $ O $ 使得 $ k_{OP}<k<k_{PQ} $ )

Code:

#include<bits/stdc++.h>
#define ll long long
#define fr(i,r) for(int i=1;i<=r;++i)
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=5e5+10,Inf=0x7fffffff;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}

int n,m;
int s[N],dp[N];

int q[N],h,t;

inline int X(int k)
{
	return s[k];
}
inline int Y(int k)
{
	return dp[k]+s[k]*s[k];
}
inline int K_nodei(int k)
{
	return 2*s[k];
}
inline int deltaX(int k1,int k2)
{
	return X(k2)-X(k1);
}
inline int deltaY(int k1,int k2)
{
	return Y(k2)-Y(k1);
}
inline bool Kjud1(int h,int i)
{
	return bool(deltaY(q[h],q[h+1])<=K_nodei(i)*deltaX(q[h],q[h+1])); //A--a--B--b--C ,b的斜率大等于a  =>   ka<=kb[已知] Δy(AB) / Δx(AB)<=kb  =>  Δy(AB)<=kb*Δx(AB)
}
inline bool Kjud2(int h,int i)
{
	return bool(deltaY(q[t],i)*deltaX(q[t-1],q[t])<=deltaY(q[t-1],q[t])*deltaX(q[t],i)); //k2<=k1   =>   y2/x2<=y1/x1   =>   y2*x1<=y1*x2
}
inline int fi(int i,int j)
{
	return dp[j]+(s[i]-s[j])*(s[i]-s[j])+m;//回到最初的定义
}

inline void init()
{
	h=t=0;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		init();
		fr(i,n) s[i]=s[i-1]+rd();
		fr(i,n)
		{
			while(h<t/*防队列退空,至少应当留有一项*/&&Kjud1(h,i)) ++h;//若前一个点到这个点的斜率<=该点的斜率要求(2*s[i]),加之斜率k单调递增,则前一个点已经无效
			dp[i]=fi(i,q[h]/*当前最优决策点*/);
			while(h<t&&Kjud2(h,i)) --t;
			q[++t]=i;
		}
		cout<<dp[n];
	}
	return 0;
}

T2&T3 #P10184.任务安排 1 P2365 任务安排 & #P10185.任务安排 2

题目描述：

给定一个含 $ n $ 个数的数列 $ C_n $ 、 $ T_n $ 和 $ S $ ,将 $ C_n $ 分为若干段 $ [a,b] $ ,求所有子段的 $ W $ 之和的最小值.

\[对于第k段[a,b]:T=k*S+\sum_{i=1}^bT_i\\ W_{k(a,b)}=(\sum^b_{i=a}C_i)*T=(\sum_{i=1}^bT_i)*(\sum^b_{i=a}C_i)+k*S*(\sum^b_{i=a}C_i) \]

$ 1<n\le 10^4 \quad 1\le S\le50 \quad 1\le T_i,C_i\le 100 $

思路：

\[\begin{align} &\quad\ 令sumC_i=\sum^i_{j=1}C_j\quad sumT_i=\sum^i_{j=1}T_j\\ &\quad\ 令f_i为前i项的最小W\\ &\therefore f_i=\min_{j=1}^{i-1}{(f_j+sumT_i*(sumC_i-sumC_j)+S*(sumC_{{\color{Red}{n}}}-sumC_j))}\\ \end{align} \]

<!!! 费用提前计算>↑

既然一次操作会使后面所有段的 $ T $ 均增加 $ S $ 且 $ S $ 只与 $ {C_i} $ 有关,那就一次性将后面所有的 $ {C_i} $ 全部进行一次更新,提前计算所需费用.

\[\begin{align} &{\color{OrangeRed}{f_i}}=\min_{j=1}^{i-1}{({\color{ForestGreen}{f_j}}+{\color{OrangeRed}{sumT_i*sumC_i}}+{\color{OrangeRed}{S*sumC_n}}-{\color{ForestGreen}{S*sumC_j}}-{\color{RoyalBlue}{sumT_i*sumC_j}})}\\ \end{align} \]

移项得:

\[\begin{align} &\boxed{{\color{ForestGreen}{f_j}}-{\color{ForestGreen}{S*sumC_j}}={\color{RoyalBlue}{sumT_i*sumC_j}}+{\color{OrangeRed}{f_i}}-{\color{OrangeRed}{sumT_i*sumC_i}}-{\color{OrangeRed}{S*sumC_n}}}\\ &\Rightarrow{\color{ForestGreen}{y}}={\color{RoyalBlue}{kx}}+{\color{OrangeRed}{b}}\\ &\boxed{\therefore y=f_j-S*sumC_j\quad {\color{Maroon}{k=sumT_i}}\quad x=sumC_j\quad {\color{Maroon}{b=f_i-sumT_i*sumC_i-S*sumC_n(目标:最小化)}}} \end{align} \]

$ \therefore\ $ 每个决策 $ j $ 都对应着一个点 $ (sumC_j,f_j-S*sumC_j) $ ,目标是使纵截距 $ b $ 最小,故维护一个下凸包.

同 $ T1 $ , $ k $ 依然满足单调递增,故可以用单调队列维护斜率 $ k $ .

同 $ T1 $ , $ x $ 值也依然满足单调递增.

Code:

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define fr(i,r) for(int i=1;i<=r;++i)
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=3e5+10,Inf=0x7fffffff;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}

int n=rd(),S=rd();
int sumC[N],sumT[N];
int q[N],h,t;
int dp[N];

inline int X(int k)
{
	return sumC[k];
}
inline int Y(int k)
{
	return dp[k]-S*sumC[k];
}
inline int K(int k)
{
	return sumT[k];
}
inline int deltaX(int k1,int k2)
{
	return X(k2)-X(k1);
}
inline int deltaY(int k1,int k2)
{
	return Y(k2)-Y(k1);
}
inline bool Kjud1(int i)
{
	return bool(deltaY(q[h],q[h+1])<=K(i)*deltaX(q[h],q[h+1]));
}
inline bool Kjud2(int i)
{
	return bool(deltaY(q[t],i)*deltaX(q[t-1],q[t])<=deltaY(q[t-1],q[t])*deltaX(q[t],i));
}
inline int Fi(int i,int j)
{
	return dp[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[n]-sumC[j]);
}
signed main()
{
	fr(i,n) sumT[i]=sumT[i-1]+rd(),sumC[i]=sumC[i-1]+rd();
	fr(i,n)
	{
		while(h<t&&Kjud1(i)) ++h;
		dp[i]=Fi(i,q[h]);
		while(h<t&&Kjud2(i)) --t;
		q[++t]=i;
	}
	cout<<dp[n];
	return 0;
}

T4 #P10186. 任务安排 3 P5785 [SDOI2012]任务安排

题目描述：

T2&T3

$ 1<n\le 3*10^5 \quad 1\le S\le2^8 \quad {\color{OrangeRed}{-2^8\le}} T_i\le 2^8 \quad 0\le C_i\le 100 $

思路：

\[\begin{align} &\boxed{{\color{ForestGreen}{f_j}}-{\color{ForestGreen}{S*sumC_j}}={\color{RoyalBlue}{sumT_i*sumC_j}}+{\color{OrangeRed}{f_i}}-{\color{OrangeRed}{sumT_i*sumC_i}}-{\color{OrangeRed}{S*sumC_n}}}\\ &\Rightarrow{\color{ForestGreen}{y}}={\color{RoyalBlue}{kx}}+{\color{OrangeRed}{b}}\\ &\boxed{\therefore y=f_j-S*sumC_j\quad {\color{Red}{k=sumT_i}}\quad x=sumC_j\quad {\color{Black}{b=f_i-sumT_i*sumC_i-S*sumC_n(目标:最小化)}}} \end{align} \]

因为 $ T_i $ 可能 $ \le 0 $ , $ k $ 不再满足单调递增,所以不能再用单调队列来维护决策点.(注意:点的 $ k $ 和线的 $ k $ 不是一个东西,因为下突壳的维护,决策点之间依然满足 $ k $ 的单调递增,不过在对每个点进行查询时 $ k $ 不单调递增,故无法顺行一次查完)
二分查找最优决策点 $ p $ ,使得 $ p $ 为满足 $ k_{\rightarrow p} <k_i $ 的最早的决策点(此时满足 $ k_{\rightarrow p}\le k_i \le k_{p\rightarrow} $ ).

其他过程同 $ T1-T3 $

Code:

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define fr(i,r) for(int i=1;i<=r;++i)
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=3e5+10,Inf=0x7fffffff;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}

int n=rd(),S=rd();
int sumC[N],sumT[N];
int q[N],h,t;
int dp[N];

inline int X(int k)
{
	return sumC[k];
}
inline int Y(int k)
{
	return dp[k]-S*sumC[k];
}
inline int K(int k)
{
	return sumT[k];
}
inline int deltaX(int k1,int k2)
{
	return X(k2)-X(k1);
}
inline int deltaY(int k1,int k2)
{
	return Y(k2)-Y(k1);
}
inline bool Kjud1(int h,int i)
{
	return bool(deltaY(q[h],q[h+1])<=K(i)*deltaX(q[h],q[h+1]));//h-->h+1斜率小于点斜率
}
inline bool Kjud2(int t,int i)
{
	return bool(deltaY(q[t],i)*deltaX(q[t-1],q[t])<=deltaY(q[t-1],q[t])*deltaX(q[t],i));
}
inline int Fi(int i,int j)
{
	return dp[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[n]-sumC[j]);
}

inline int bin_search(int i)
{
	int l=h,r=t;//<-1 x>
	while(l<r)
	{
		int mid=(l+r)>>1;//检查线段mid-->mid+1斜率
		if(Kjud1(mid,i)) l=mid+1;
		else r=mid;//<-1 x>
	}
	return q[l];
}

int p;
signed main()
{
	fr(i,n) sumT[i]=sumT[i-1]+rd(),sumC[i]=sumC[i-1]+rd();
	fr(i,n)
	{
		p=bin_search(i);
		dp[i]=Fi(i,p);
		while(h<t&&Kjud2(t,i)) --t;
		q[++t]=i;
	}
	cout<<dp[n];
	return 0;
}

T5 #P10188. 玩具装箱 P3195 玩具装箱

题目描述：

给定一个数列 $ C_n $ 和一个常数 $ L $ ,将其分为若干 $ (k1) $ 段,对于其中一段 $ t=[i,j] $ ,

\[\begin{align} &W_{t=[i,j]}=[(j-i+\sum^j_{k=i}C_k)-L]^2\\ &W=\sum_{i=1}^{k1} W_t \end{align} \]

求 $ W $ 的最小值.

$ 1\le n\le 5*10^4\quad 1\le L \le 10^7\quad 1\le C_i\le 10^7 $

思路：

\[\begin{align} &\quad\ 令S_n=\sum_{i=1}^nC_n\\ &\therefore W_{j}=(i-j+S_i-S_{j-1}-L)^2\\ &\quad\ 令f_i为前i项的最小W\\ &\therefore f_i=\min_{j=2}^{i}{(f_{j-1}+i^2+j^2+……)}\qquad //显然太复杂\\ \end{align} \]

\[\begin{align} &\quad\ 令S_n=\sum_{i=1}^nC_n+n\qquad //优化\\ &\therefore W_{j+1,i}=(S_i-S_j-(L+1))^2\\ &\qquad\ f_i=\min_{j=1}^{i-1}{(f_j+S_{j}^2+2*(L+1)*S_{j}-2*S_i*S_{j}+S_i^2-2*(L+1)*S_i+(L+1)^2)}\\\\ &\boxed {{\color{ForestGreen}{f_j}}+{\color{ForestGreen}{S_{j}^2}}+{\color{ForestGreen}{2*(L+1)*S_{j}}}={\color{RoyalBlue}{(2*S_i)*S_{j}}}+{\color{OrangeRed}{f_i}}-{\color{OrangeRed}{S_i^2+2*(L+1)*S_i}}-{\color{OrangeRed}{(L+1)^2}}}\\ &\boxed{\therefore y=f_j+S_{j}^2+2*(L+1)*S_{j}\quad k=2*S_i\quad x=S_{j}\quad b=f_i-S_i^2+2*(L+1)*S_i-(L+1)^2} \end{align} \]

* $ T1 $ 提到的移项方法是一种通法,但一个式子可能不止一种移项方法,不同移法的 $ y,k,x,b $ 可能会有所不同,但结果相同:

\[\begin{align} &\quad\ 令S_n=\sum_{i=1}^nC_n+n\qquad //优化\\ &\therefore W_{j+1,i}=(S_i-S_j-(L+1))^2\\ &\qquad\ f_i=\min_{j=1}^{i-1}{(f_j+S_{j}^2+2*(L+1)*S_{j}-2*S_i*S_{j}+S_i^2-2*(L+1)*S_i+(L+1)^2)}\\\\ &\boxed {{\color{ForestGreen}{f_j}}+{\color{ForestGreen}{S_{j}^2}}={\color{RoyalBlue}{(2*S_i-2*(L+1))*S_{j}}}+{\color{OrangeRed}{f_i}}-{\color{OrangeRed}{S_i^2+2*(L+1)*S_i}}-{\color{OrangeRed}{(L+1)^2}}}\\ &\boxed{\therefore y=f_j+S_{j}^2\quad k=2*S_i-2*(L+1)\quad x=S_{j}\quad b=f_i-S_i^2+2*(L+1)*S_i-(L+1)^2} \end{align} \]

(还有更多方法)

本题需要维护 $ b $ 值最小,故维护一个下凸包.

其余同 $ T2 $ .

Code:

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define fr(i,r) for(int i=1;i<=r;++i)
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=5e4+10,Inf=0x7fffffff;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}

int n=rd(),L=rd();
int S[N];
int q[N],h,t;
int dp[N];

inline int X(int j)
{
	return S[j];
}
inline int Y(int j)
{
	return dp[j]+S[j]*S[j]+2*(L+1)*S[j];
}
inline int K(int i)
{
	return 2*S[i];
}
inline int deltaX(int k1,int k2)
{
	return X(k2)-X(k1);
}
inline int deltaY(int k1,int k2)
{
	return Y(k2)-Y(k1);
}
inline bool Kjud1(int i)
{
	return bool(deltaY(q[h],q[h+1])<=K(i)*deltaX(q[h],q[h+1]));
}
inline bool Kjud2(int i)
{
	return bool(deltaY(q[t],i)*deltaX(q[t-1],q[t])<=deltaY(q[t-1],q[t])*deltaX(q[t],i));
}
inline int Fi(int i,int j)
{
	return dp[j]+(S[i]-S[j]-(L+1))*(S[i]-S[j]-(L+1));
}
signed main()
{
	fr(i,n) S[i]=S[i-1]+rd()+1;
	fr(i,n)
	{
		while(h<t&&Kjud1(i)) ++h;
		dp[i]=Fi(i,q[h]);
		while(h<t&&Kjud2(i)) --t;
		q[++t]=i;
	}
	cout<<dp[n];
	return 0;
}

T6 P3648 [APIO2014]序列分割

题目描述：

思路：

Code:

T7 P

题目描述：

思路：

Code: