首页 > 代码库 > 【BZOJ1911】【Apio2010】特别行动队,斜率优化DP裸题(斜率有单调性)

【BZOJ1911】【Apio2010】特别行动队,斜率优化DP裸题(斜率有单调性)

题解:

首先裸dp方程为:

F(x)=a*x*x+b*x+c;  sum为前缀和

f[i]=f[j]+F(sum[i]-sum[j]);


然后拆开后把带j的放一边,带i的放一边,形成y=kx+b的形式,使y和x都含j不含i,k和b都含i不含j。

得:f[j]+asum[j]*sum[j]-b*sum[j]=2*a*sum[i]*sum[j]+f[i]-a*sum[i]*sum[i]-b*sum[i]-c;

然后有:y=kx+b;

y=f[j]+asum[j]*sum[j]-b*sum[j];

x=sum[j];

k=2*a*sum[i];

b=f[i]-a*sum[i]*sum[i]-b*sum[i]-c;


然后显然可以观察到,每个j处理出来一个x和y,则可以在坐标系中进行表示。

而若有一个i,则又可以处理出“k”,那么这样就可以算出来b的值。

而已知i,通过b的值我们又可以算出来f[i]的值。


b为截距,那么本题中b与f[i]就成正比。我们可以先画出一个斜率为k,经过j抽象出来的点J的直线帮助理解。

显然,这个截距需要尽量大以保证答案。


随后我们需要根据点维护一个凸包,可以脑补一下,凸包内的点不可能更优(这个不细说了),而我们要找的则是一个凸点P,使得我们先把直线放在无限高处,然后向下平移,接触到的凸包上的第一个点。

通过画图可以直观地发现:斜率为k的直线经过点P时有对于当前“i”的最大截距。


即对于当前“i”,这个P代表的“j”是动规方程f[i]=f[j]+F(sum[i]-sum[j])的可以转移来的最优的j,

即任意通过k(k!=j)转移来的f[i]都要小于通过j转移过来的f[i]。


一般情况下我们可以二分来找到这个凸点P,但是有些时候斜率满足单调性,我们就可以利用类似单调队列的维护方法对凸包进行维护,如本题,一旦队列头的一点对于i处理出来的斜率k劣于队列中的第二个点,就把头出队,这样出队操作完成后就可以取队头为i的最优决策j了。


然后决策完成后我们就得到了f[i],就又可以处理出i的“x”和“y”,这时再把它加入到凸包中就好了。

呃,凸包就不多说了。


贴代码,这个代码挺清晰的~~~(维护的上凸包。。。。)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define X(x) (sum[x])
#define Y(x) (f[x]+a*sum[x]*sum[x]-b*sum[x])
#define K(x) (2*a*sum[x])
#define F(x) (a*x*x+b*x+c)
using namespace std;
int L,R,n,a,b,c;
long long sum[N],f[N];
struct Point
{
	long long x,y;
	int id;
	Point(long long _x,long long _y,int _id):x(_x),y(_y),id(_id){}
	Point(){}
}que[N],now;
inline long long xmul(Point i,Point j,Point k){return (j.x-k.x)*(i.y-k.y)-(j.y-k.y)*(i.x-k.x);}
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k;
	scanf("%d%d%d%d",&n,&a,&b,&c);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&sum[i]),sum[i]+=sum[i-1];
		k=K(i);
		while(L<R&&que[L].y-k*que[L].x<que[L+1].y-k*que[L+1].x)L++;
		f[i]=f[que[L].id]+F((sum[i]-sum[que[L].id]));
		now=Point(X(i),Y(i),i);
		while(L<R&&xmul(now,que[R],que[R-1])>=0)R--;
		que[++R]=now;
	}
	cout<<f[n]<<endl;
	return 0;
}



【BZOJ1911】【Apio2010】特别行动队,斜率优化DP裸题(斜率有单调性)