联赛模拟测试18 A. 施工 单调队列（栈）优化DP

题目描述

分析

• 对于 \(Subtask\ 1\),可以写一个 \(n^3\) 的 \(DP\)，\(f[i][j]\) 代表第 \(i\) 个建筑高度为 \(j\) 时的最小花费，随便转移即可
  
  时间复杂度 \(O(n \times h^2)\)
• 对于 \(Subtask\ 2\)，我们沿用 \(Subtask\ 1\)的思路，记录前缀后缀 \(min\)，将复杂度优化至 \(O(n \times h)\)
  
  但是显然两维的定义无法继续进行优化，我们可以考虑改变一下定义的方式
  
  设 \(f[i]\) 表示考虑前 \(i\) 个建筑,并且第 \(i\) 个建筑高度不变的最优答案
  
  可以发现，枚举两个不变的边界,那么中间的建筑必定被提高成相同的小于等于边界的高度
  
  也就是说我们需要把一些坑填平
  
  因为增加峰的高度既花人力又不能提高观赏度
  
  增加坡的高度花人力但不能提高观赏度
  
  只有增加坑的高度才会有贡献，而且增加的值不能超过边界的高度
  
  因为超过边界的高度又变成了峰
  
  因此我们可以枚举边界然后再枚举填平的高度
  
  转移方程为 \(f[i]=f[j]+(sum2[i-1]-sum2[j])+(i-j-1)*h*h-(sum1[i-1]-sum1[j])*2*h+c*abs(a[i]+a[j]-2*h)\)
  
  其中 \(sum1[i]\) 为 \(a\) 数组的前缀和，\(sum2[i]\) 为 \(a\) 数组平方的前缀和
  
  上面的式子是展开后的式子，原式子并不难推
  
  注意这种做法我们需要把 \(a[0]\) 和 \(a[n+1]\) 置为无穷大，因为我们有可能提高第一个和最后一个建筑的高度
  
  要特判 \(i,j\) 等于 \(0\)或 \(n+1\) 的情况
  
  最后的答案为 \(f[n+1]\)
  
  时间复杂度 \(O(n^2 \times h)\),不知道为什么能过这个子任务
• 对于 \(Subtask\ 3\)，我们把一维 \(DP\) 的状态转移方程化简得到
  
  \(f[i]=f[j]+(i-j-1)*h*h-2*(sum1[i-1]-sum1[j]+c)*h+(sum2[i-1]-sum2[j])+c*(a[i]+a[j])\)
  
  我们发现前半部分是一个关于高度 \(h\) 的二次函数
  
  可以直接由对称轴求出最小值
  
  时间复杂度 \(O(n^2)\)
• 对于 \(Subtask\ 4\) 和 \(Subtask\ 5\)，我们会发现只有两个高度较大的建筑夹着一堆高度较小的建筑才有贡献
  
  因此可以用单调队列（栈）维护
  
  时间复杂度 \(O(n logn)\)
  
  复杂度的瓶颈在\(ST\) 表查询最值上

代码

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<iostream>

#include<cstring>

#define rg register

inline int read(){

	rg int x=0,fh=1;

	rg char ch=getchar();

	while(ch<'0' || ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0' && ch<='9'){

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*fh;

}

typedef long long ll;

const int maxn=1e6+5;

int n,c,a[maxn],maxh,lg[maxn],st[maxn][22],head,tail,q[maxn];

ll f[maxn],sum1[maxn],sum2[maxn];

int zhao(ll i,ll j){

	if(j==0 && i==n+1) return ((double)(sum1[i-1]-sum1[j])/(double)(i-j-1)+0.5);

	else if(j==0 || i==n+1) return ((double)(2*sum1[i-1]-2*sum1[j]+c)/(double)(2.0*(i-j-1))+0.5);

	return ((double)(c+sum1[i-1]-sum1[j])/(double)(i-j-1)+0.5);

}

int cx(int l,int r){

	rg int k=lg[r-l+1];

	return std::max(st[l][k],st[r-(1<<k)+1][k]);

}

int main(){

	memset(f,0x3f,sizeof(f));

	n=read(),c=read();

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

		a[i]=read();

		maxh=std::max(maxh,a[i]);

		sum1[i]=sum1[i-1]+a[i];

		sum2[i]=sum2[i-1]+1LL*a[i]*a[i];

		st[i][0]=a[i];

	}

	for(rg int i=2;i<=n;i++){

		lg[i]=lg[i/2]+1;

	}

	for(rg int j=1;j<=20;j++){

		for(rg int i=1;i+(1<<j)-1<=n;i++){

			st[i][j]=std::max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

		}

	}

	a[0]=a[n+1]=0x3f3f3f3f;

	f[0]=f[1]=0;

	head=1,tail=1;

	rg int mmax,mmin,now;

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

		while(head<=tail){

			if(q[tail]==i-1){

				if(i<=n) f[i]=std::min(f[i],f[q[tail]]+1LL*c*std::abs(a[i]-a[i-1]));

				else f[i]=f[i-1];

			} else {

				mmax=cx(q[tail]+1,i-1);

				mmin=std::min(a[i],a[q[tail]]);

				if(mmin>=mmax){

					now=zhao(i,q[tail]);

					if(now<mmax) now=mmax;

					if(now>mmin) now=mmin;

					if(q[tail]==0 && i==n+1) f[i]=std::min(f[i],f[q[tail]]+1LL*(i-q[tail]-1)*now*now-2LL*(sum1[i-1]-sum1[q[tail]])*now+1LL*(sum2[i-1]-sum2[q[tail]]));

					else if(q[tail]==0) f[i]=std::min(f[i],f[q[tail]]+1LL*(i-q[tail]-1)*now*now-1LL*(2*sum1[i-1]-2*sum1[q[tail]]+c)*now+1LL*(sum2[i-1]-sum2[q[tail]])+1LL*c*a[i]);

					else if(i==n+1) f[i]=std::min(f[i],f[q[tail]]+1LL*(i-q[tail]-1)*now*now-1LL*(2*sum1[i-1]-2*sum1[q[tail]]+c)*now+1LL*(sum2[i-1]-sum2[q[tail]])+1LL*c*a[q[tail]]);

					else f[i]=std::min(f[i],f[q[tail]]+1LL*(i-q[tail]-1)*now*now-2LL*(sum1[i-1]-sum1[q[tail]]+c)*now+1LL*(sum2[i-1]-sum2[q[tail]])+1LL*c*(a[i]+a[q[tail]]));

				}

			}

			if(a[i]>=a[q[tail]])tail--;

			else break;

		}

		q[++tail]=i;

	}

	printf("%lld\n",f[n+1]);

	return 0;

}