lp4027 NOI2007 货币兑换

我们观察到,整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得:
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说,购买的A和B券的数量分别是:
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么,我们从j转移到i的方程是:
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设:
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$
那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。
通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意:要判一下分母不能等于极小数,否则可能会挂。

略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得: $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说,购买的A和B券的数量分别是: $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么,我们从j转移到i的方程是: $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设: $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$ 那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。 通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意:要判一下分母不能等于极小数,否则可能会挂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
	double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。 
inline double cmp(const data &A,const data &B){
	return A.a*B.b>B.a*A.b; 
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
//	printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
	return a[P].x*A+a[P].y*B; 
}
inline double slp(int A,int B){
	if(fabs(a[A].x-a[B].x)<eps){
		return INF;
	}
	return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
	int mid=(l+r)>>1;
	int I=l,J=mid+1,tp=l;
	while(I<=mid&&J<=r){
		if(a[I].x<a[J].x){
			b[tp++]=a[I++];
		}else{
			b[tp++]=a[J++];
		}
	}
	while(I<=mid){
		b[tp++]=a[I++];
	}
	while(J<=r){
		b[tp++]=a[J++];
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
}
inline void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],f[l-1]);
		a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
		a[l].x=(double)a[l].r*a[l].y;
		return;
	}
	int mid=(l+r)>>1;
	int I=l,J=mid+1;
	for(int i=l;i<=r;++i){
		if(a[i].id<=mid){
			b[I++]=a[i];
		}else{
			b[J++]=a[i];
		}
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
	cdq(l,mid);
	tp=0;
	for(int i=l;i<=mid;++i){
		while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
			--tp;
		}
		st[++tp]=i;
	}
//	printf("[%d,%d]\n",l,r);
//	for(int i=1;i<=tp;++i){
//		printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
//	}
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
			--tp;
		}
		f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
//		printf("%d %lf\n",i,a[i].ans); 
	}
	cdq(mid+1,r);
	mg(l,r);
}
void init(){
	scanf("%d%lf",&n,&f[0]);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	cdq(1,n);
//	for(int i=1;i<=n;++i){
//		printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
//	}
	printf("%.3lf\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp3648 APIO2014 序列分割

首先证明序列分割的次序和最后的答案毫无关系。
这可以用乘法的基本性质证明。例如分成三段,我们有:
$$a(b+c)+bc=b(a+c)+ac$$

我们可以进行DP。
我们记\(f_{i,k}\)表示当前访问到第\(i\)个点,使用了\(k\)次切割的答案。
那么根据题目中贡献的定义,我们有:
$$f_{i,k}=max_{j=k}^{i-1}{f_{j,k-1}+sm_{j}(sm_{i}-sm_{j})}$$ 令\(k\le j_1(sm_i-sm_{j_1})\le f_{j_2,k-1}+sm_{j_2}(sm_i-sm_{j_2})\)$ 展开,移项,合并。 $$f_{j_1,k-1}+sm_{j_1}sm_i-sm_{j_1}^2\le f_{j_2,k-1}+sm_{j_2}sm_i-sm_{j_2}^2$$ $$f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2\le sm_{j_2}sm_i-sm_{j_1}*sm_i$$
$$\frac{f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2}{sm_{j_2}-sm_{j_1}}\le sm_i$$
这个式子显然是可以斜率优化的。
这样做的时空复杂度是\(O(nk)\)的。
考虑到这一题的空间限制比较紧张,我们可以用滚动数组把\(k\)这一维压掉。

#include<iostream>
#include<cstdio>

int q[100005];
long long f[100005][2],sm[100005];
int ans[100005][205],n,K;
inline double slope(int j1,int j2,int k){
	return (sm[j1]^sm[j2])?(double)(f[j1][(k&1)^1]-f[j2][(k&1)^1]+sm[j2]*sm[j2]-sm[j1]*sm[j1])/(double)(sm[j2]-sm[j1]):-1E18;
} 
void init(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;++i){
		scanf("%lld",&sm[i]);
		sm[i]+=sm[i-1];
	}
	for(int i=1;i<=K;++i){
		int l,r;
		l=r=1;
		for(int j=1;j<=n;++j){
			while(l<r&&slope(q[l],q[l+1],i)<=sm[j]){
				++l;
			}
			f[j][i&1]=f[q[l]][(i&1)^1]+sm[q[l]]*(sm[j]-sm[q[l]]);
			ans[j][i]=q[l];
			while(l<r&&slope(q[r-1],q[r],i)>slope(q[r],j,i)){
				--r;
			}
			q[++r]=j;
		}
	}
	int nw=n;
	printf("%lld\n",f[n][K&1]);
	for(int i=K;i>=1;--i){
		nw=ans[nw][i];
		printf("%d ",nw);
	}
}

int main(){
	init();
	return 0;
}

lp3195 HNOI2008 玩具装箱TOY

一道斜率优化的经典例题。
对于这道题,DP式是容易得到的:
$$f_i=min\{f_j+(\sum_{j+1}^ia_{i}+i-j-1-L)^2\}$$
前缀和优化:
$$f_i=min\{f_j+(sm_i-sm_j+i-j-1-L)^2\}$$
考虑到这是一个与取值平方相关的式子,尝试用斜率优化来化简。
令:
$$u_i=sm_i+i$$
$$f_i=min{f_j+(u_i-u_j-1-L)^2}$$
对于右式,我们假定\(1\le j<k<i\)且从\(k\)转移较优。
那么我们有:
$$f_{k}+(u_{i}-u_{k}-1-L)^2\le f_{j}+(u_{i}-u_{j}-1-L)^2$$
展开并移项化简:
$$2u_{i}(u_{j}-u_{k})\le f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2$$
令:
$$g_{i}=(u_{i}+1+L)^2$$
并不妨假定:
$$u_{j}!=u_{k}$$
可得:
$$2u_{i}\le\frac{f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2}{(u_{j}-u_{k})}$$
故而,若要使得答案更大,则上式必然成立。
考虑到这个式子符合单调队列的性质,我们可以上一个类似单调队列的数据结构来维护右侧的式子,也就是俗称的“斜率”。
这就完成了斜率优化。

#include<iostream>
#include<cstdio>
#include<queue>


int n,L;
double sm[50005],f[50005];
int q[50005],l,r;
inline double u(int X){
	return sm[X]+X;
}
inline double g(int X){
	return u(X)+L+1;
}
inline double x(int X){
	return g(X);
}
inline double y(int X){
	return f[X]+g(X)*g(X);
}
inline double k(int A,int B){
	return (y(A)-y(B))/(x(A)-x(B));
}

void init(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;++i){
		scanf("%lf",&sm[i]);
		sm[i]+=sm[i-1];
	}
	l=r=1;
	for(int i=1;i<=n;++i){
		while(l<r&&k(q[l],q[l+1])<2*u(i)){
			++l; 
		} 
		f[i]=f[q[l]]+(u(i)-g(q[l]))*((u(i)-g(q[l])));
		while(l<r&&k(i,q[r-1])<k(q[r-1],q[r])){
			--r;
		}
		q[++r]=i;
	}
	printf("%lld\n",(long long)f[n]);
}

int main(){
	init();
	return 0;
}