【BZOJ3156】防御准备（动态规划，斜率优化）

题面

题解

从右往左好烦啊，直接\(reverse\)一下再看题。

设\(f[i]\)表示第\(i\)个位置强制建立检查站时，前面都满足条件的最小代价

\(f[i]=min(f[j]+sum[i-j-1])+A[i]\)

即枚举上一个检查站建立的位置。

假设存在\(k,j\)满足\(k<j\)，并且\(j\)的转移优于\(k\)的转移。

那么\(f[j]+sum[i-j-1]<f[k]+sum[i-k-1]\)

因为\(sum\)这个和\(i,j,k\)有关，所以把它拆分一下，变成之与\(i\)以及只与\(j\)相关的式子

\(sum[i-j-1]=\sum_{k=1}^{i-j-1}k=sum[i-1]-sum[j]-(i-j-1)*j\)

然后再放回到上面的不等式。

即\(f[j]-sum[j]-(i-j-1)*j\lt f[k]-sum[k]-(i-k-1)*k\)

按照是否和\(i\)有关对于式子分类

\((f[j]-sum[j]+j^2+j)-(f[k]-sum[k]+k^2+k)\lt (j-k)*i\)

令\(g[i]=f[i]-sum[i]+i^2+i\)

直接除过去

\[i\gt \frac{g[j]-g[k]}{j-k}
\]

因为\(i\)单增，所以可以利用单调队列来完成斜率优化。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 1111111

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

ll f[MAX],s[MAX];

int n,a[MAX];

int Q[MAX],h,t;

double Slope(int i,int j){return ((f[i]-s[i]+1.0*i*i+i)-(f[j]-s[j]+1.0*j*j+j))/(i-j);}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read();

	reverse(&a[1],&a[n+1]);

	for(int i=1;i<=n;++i)s[i]=s[i-1]+i;

	/*

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

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

			f[i]=min(f[i],f[j]+s[i-1]-s[j]-j*(i-j-1)+a[i]);

	*/

	Q[h=t=1]=1;f[1]=a[1];

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

	{

		while(h<t&&Slope(Q[h],Q[h+1])<=i)++h;

		int j=Q[h];f[i]=f[j]+s[i-1]-s[j]-j*(i-j-1)+a[i];

		while(h<t&&Slope(Q[t],Q[t-1])>=Slope(Q[t-1],i))--t;

		Q[++t]=i;

	}

	for(int i=1;i<=n;++i)f[n]=min(f[n],f[i]+s[n-i]);

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

	return 0;

}

巴特西

【BZOJ3156】防御准备（动态规划，斜率优化）

【BZOJ3156】防御准备（动态规划，斜率优化）

题面

题解

最新文章

热门文章