bzoj 2216: [Poi2011]Lightning Conductor【决策单调性dp+分治】

参考：https://blog.csdn.net/clove_unique/article/details/57405845

死活不过样例看了题解才发现要用double....

\[a_j \leq a_i+p-\sqrt{abs(i-j)}
\]

\[p\geq a_j+\sqrt{abs(i-j)}-a_i
\]

\[p = max\{a_j+\sqrt{abs(i-j)}\}-a_i
\]

\[f_i+a_i = max\{a_j+\sqrt{abs(i-j)}\}
\]

首先正反做两遍，这样就不用考虑绝对值了，答案直接从正反连个数组取max即可

然后看这个转移，发现i-j是递增的，也就是j的取值是单调向右移动的

用分治来做dp

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=500005;

int n;

double a[N],s[N],f[N],g[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void wk(double f[],int l,int r,int x,int y)

{//cerr<<l<<" "<<r<<"   "<<x<<" "<<y<<endl;

	if(x>y||l>r)

		return;

	int mid=(l+r)>>1,w;

	double p;

	for(int i=x;i<=y&&i<=mid;i++)

		if((p=a[i]+s[mid-i])>f[mid])

		{

			w=i;

			f[mid]=p;

		}

	f[mid]-=a[mid];

	wk(f,l,mid-1,x,w);

	wk(f,mid+1,r,w,y);

}

int main()

{

	n=read();

	for(int i=1;i<=n;i++)

		a[i]=read(),s[i]=sqrt((double)i);

	wk(f,1,n,1,n);

	for(int i=1;i<=n/2;i++)

		swap(a[i],a[n-i+1]);

	wk(g,1,n,1,n);

	for(int i=1;i<=n;i++)

		printf("%.0lf\n",ceil(max(f[i],g[n-i+1])));

	return 0;

}

巴特西

bzoj 2216: [Poi2011]Lightning Conductor【决策单调性dp+分治】

最新文章

热门文章