斜率优化解题报告(uoj转)

任务安排1~3：

模版。用到一个著名的思想：费用提前计算。

暴力维数高的原因是不能较快的知道前面分了几批

但是一旦分了一批，对后面都会有\(S\)的时间叠加

所以不妨设\(f_i\)表示已知会花费的时间min，

\(f_i = \min_{j=1}^{i-1} f_j + (SC_i-SC_j) \cdot ST_i + S \cdot (SC_n-SC_j)\)

\(O(n^2)\)通过T1.

大力拆式子，发现有一个叫做\(ST_i \cdot SC_j\)的玩意，i,j之间无法独立

不慌，还是先移项，得

\(f_j-SC_j \cdot S = ST_i \cdot SC_j + f_i - ST_i \cdot SC_i - S \cdot SC_n\)

\(i\)为常数，\(j\)为变量的话此为一次函数，维护下凸包即可

关于为何是下凸包：

1.直观理解：下面的截距才小，\(f_i\)才小

2.线性规划的结论证明

3.分类讨论证明

能理解就行

这样2、3都秒了，只是在单调队列中取哪个做答案的问题

其实还可以有4，\(T_i\)也能是负数

在凸包中间插点，set维护即可

B. Cats Transport

乍一看很难搞，两三个属性

分析一波，若feeder(\(t\)时刻出发)接到了一只cute cat，则它应该等待\(t+SD_i-T_i\)分钟（\(t \geq T_i -SD_i\)）

所以可设\(a_i = T_i - SD_i\)并排序

不难发现\(a\)小的cat应由出发早的人接

人少，可设\(f_{i,j}\)表示前\(i\)个人接走前\(j\)个cat最小时间

\(f_{i,j}=f_{i-1,k}+(j-k)*Sa_j-(Sa_j-Sa_k)\)

（贪心设置的t,无需多言)

\(i\)直接滚掉，移项得

\(pre_j + Sa_j = j \cdot Sa_i + f_i + (i-1) \cdot Sa_i\)

结束战斗

P3195 [HNOI2008]玩具装箱

套路了。。。

\(f_i\)表示前\(i\)个分好最小代价

设\(s_i = \sum_{j=1}^i c_j\)

\(f_i = f_j + (s_i-s_j+i-j-1-L)^2\)

设\(a_i=s_i+i\) , \(R = 1 - L\) , 则

\(f_i = f_j + (a_i - a_j + R)^2\),

化简即可不想写了

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
#define ll long long
int n,q[N],hh,tt;
ll f[N],s[N],D;
ll get_y(int j){
	return f[j]+(s[j]-D)*(s[j]-D);
}
int main(){
	scanf("%d%lld",&n,&D);
	D=-1ll-D;
	fr(i,1,n){
		scanf("%lld",&s[i]);
		s[i]+=s[i-1]; 
	}
	fr(i,1,n)s[i]+=1ll*i;
	fr(i,1,n){
		while(hh<tt&&(get_y(q[hh+1])-get_y(q[hh]))<2ll*s[i]*(s[q[hh+1]]-s[q[hh]]))hh++;
		f[i]=f[q[hh]]+1ll*(s[i]-s[q[hh]]+D)*(s[i]-s[q[hh]]+D); 
		while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(s[i]-s[q[tt]])>=(get_y(i)-get_y(q[tt]))*(s[q[tt]]-s[q[tt-1]]))tt--;
		q[++tt]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

P2120 [ZJOI2007]仓库建设

\(f_i\)表示前\(i\)个的min

\(f_i = \min_{j=1}^{i-1} (f_j + c_i + x_i \cdot (Sp_i - Sp_j) - (Sxp_i - Sxp_j))\)

tips:其实不需要把整个式子拆开，只需观察出\(x\),\(y\),\(Slope\)即可

还是很好找的

注意此时钦定了\(n\)号位必建仓库，特判即可

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 1000005
#define ll __int128
int n,q[N],hh,tt;
ll f[N],x[N],c[N],Sp[N],Sxp[N];
ll get_y(int j){
	return f[j]+Sxp[j];
}
int main(){
	scanf("%d",&n);
	int tmp,tmp1,tmp2,fl=0;
	fr(i,1,n){
		scanf("%d%d%d",&tmp1,&tmp,&tmp2);
		x[i]=tmp1,c[i]=tmp2;
		Sp[i]=Sp[i-1]+tmp;
		Sxp[i]=Sxp[i-1]+x[i]*tmp;
		if(i==n&&tmp==0)fl=1;
	}
	fr(i,1,n){
		while(hh<tt&&(get_y(q[hh+1])-get_y(q[hh]))<(Sp[q[hh+1]]-Sp[q[hh]])*x[i])hh++;
		f[i]=f[q[hh]]+c[i]+x[i]*(Sp[i]-Sp[q[hh]])-(Sxp[i]-Sxp[q[hh]]);
		while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(Sp[i]-Sp[q[tt]])>=(get_y(i)-get_y(q[tt]))*(Sp[q[tt]]-Sp[q[tt-1]]))tt--;
		q[++tt]=i;
	}
	printf("%lld\n",(long long)f[n]-fl*c[n]);
	return 0;
}

P3628 [APIO2010]特别行动队

一时竟分不清哪个是模版

\(f_i = f_j + A(s_i - s_j)^2+B(s_i-s_j) + C\)

《不难看出》,
\(y = f_j + As_j^2-Bs_j\) ,
\(x = s_j\) , \(Slope = 2As_i\)

舒服~

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 1000005
#define ll long long
int n,q[N],hh,tt;
ll s[N],f[N],A,B,C;
ll get_y(int j){
	return f[j]+A*s[j]*s[j]-B*s[j];
}
int main(){
	scanf("%d%lld%lld%lld",&n,&A,&B,&C);
	ll x;
	fr(i,1,n){
		scanf("%lld",&x);
		s[i]=s[i-1]+x;
	}
	fr(i,1,n){
		while(hh<tt&&get_y(q[hh+1])-get_y(q[hh])>(s[q[hh+1]]-s[q[hh]])*2ll*A*s[i])hh++;
		int j=q[hh];
		f[i]=f[j]+A*(s[i]-s[j])*(s[i]-s[j])+B*(s[i]-s[j])+C;
		while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(s[i]-s[q[tt]])<=(get_y(i)-get_y(q[tt]))*(s[q[tt]]-s[q[tt-1]]))tt--;
		q[++tt]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

P4360 [CEOI2004]锯木厂选址

可以看出考虑\(f_i\)表示\(i\)处已经有一个兜底，还能再建一个，运完前\(i\)个最小代价

则\(f_i\)

\(= \min_{j=1}^{i-1}(\sum_{k=1}^j(x_j-x_k) \cdot p_k+\sum_{k=j+1}^i(x_i-x_k) \cdot p_k)\)

\(= x_j\sum_{k=1}^j p_k+x_i\sum_{k=j+1}^i p_k -\sum_{k=1}^i x_k \cdot p_k\)

\(= x_j \cdot Sp_j + x_i \cdot Sp_i - x_i \cdot Sp_j - Sxp_i\)

整理得

\(x_j \cdot Sp_j = x_i \cdot Sp_j + f_i - x_i \cdot Sp_i + Sxp_i\)

没有\(f_j\)好害怕

一样嘛，就是把只有\(j\)的全移到左边当\(y\)，\(ij\)乘积项当\(x\)，其余截距，这是精髓

求出\(f_i\)，\(ans = \min_{i=1}^n (f_i + \sum_{j=i+1}^n(x_{n+1}-x_j) \cdot p_j)\)

小发现：\(\sum x \cdot p\)可以最后一起算

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 20005
#define ll long long
int n,q[N],hh,tt;
ll ans=1e18,f[N],x[N],p[N],res;
ll get_y(int j){
	return x[j]*p[j];
}
int main(){
	scanf("%d",&n);
	ll tmp;
	fr(i,1,n){
		scanf("%lld%lld",&p[i],&tmp);
		res+=x[i]*p[i];
		p[i]+=p[i-1];
		x[i+1]=x[i]+tmp;
	}
	fr(i,1,n){
		while(hh<tt&&get_y(q[hh+1])-get_y(q[hh])<(p[q[hh+1]]-p[q[hh]])*x[i])hh++;
		f[i]=x[i]*p[i]+p[q[hh]]*(x[q[hh]]-x[i]);
		while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(p[i]-p[q[tt]])>(get_y(i)-get_y(q[tt]))*(p[q[tt]]-p[q[tt-1]]))tt--;
		q[++tt]=i;
		ans=min(ans,f[i]+x[n+1]*(p[n]-p[i]));
	}
	printf("%lld\n",ans-res);
	return 0;
}

完结撒电脑