【BZOJ3156】防御准备

发表于 | 分类于 ， | 评论数： | 阅读次数：
斜率优化模板题

1

2

这道题是斜率优DP的模板题，非常基础，但是我们内部测试的时候我推的式子把一个$+$写成了$-$，然而暴力也写错了，所以没有分。

方程：

$f_i=\min{f_j+\displaystyle\sum_{k=j+1}^{i-1}{i-k}}+a_i$

其中$f_i$表示到第i个地方我们建塔的最小花费，那么枚举的j就是上一个建塔的地方，这里认为$j+1..i-1$的地方都不建造塔，都放木偶，所以木偶的花费就在dp式子中间的那个求和符号那里计算，最后加上当前建造塔的花费。

容易变形得到：

$f_i=\min{f_j+\frac{(i-j)\times(i-j-1)}{2}}+a_i$

注意这里拆括号时加减号不要像我那样写错。

拆括号：

$f_i=f_j+\frac{i^2-i}{2}+\frac{j^2+j}{2}-i\times j+a_i$

继续变形，把j的放一边，i的放一边。

$f_j+\frac{j^2+j}{2}=i\times j+f_i-\frac{i^2-i}{2}+a_i$

此时，发现这是可以斜率优化的式子。感性理解为一个平面直角坐标系中的一个凸包即可，令$y=f_j+\frac{j^2+j}{2},k=i,x=j,b=f_i-\frac{i^2-i}{2}+a_i$即可。

这是最终的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
using namespace std;

const int maxn=1000010;
typedef long long ll;
int n,l,r,q[maxn],a[maxn];
ll f[maxn];

ll gety(int j)
{
	return 1ll*(f[j]+(1ll*j*(j+1)>>1));
}

ll getans(int i,int j)
{
	return 1ll*(f[j]+(1ll*(i-j)*(i-j-1)>>1)+a[i]);
}

int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<48||c>57)
		f=c=='-'?-1:1,c=getchar();
	while (c>=48&&c<=57)
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

int main()
{
	int i;
	n=read();
	for (i=1;i<=n;i++)
		a[i]=read();
	q[l=r=1]=0;
	for (i=1;i<=n;i++)
	{
		while (l<r&&(gety(q[l+1])-gety(q[l]))<=1ll*i*(q[l+1]-q[l]))
			l++;
		f[i]=getans(i,q[l]);
		while (l<r&&1ll*(gety(q[r])-gety(q[r-1]))*(i-q[r])>=1ll*(gety(i)-gety(q[r]))*(q[r]-q[r-1]))
			r--;
		q[++r]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

这是对拍用的暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
using namespace std;

const int maxn=1000010;
typedef long long ll;
int n,a[maxn];
ll f[maxn];

#define min(a,b) (a<b?a:b)

int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<48||c>57)
		f=c=='-'?-1:1,c=getchar();
	while (c>=48&&c<=57)
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

int main()
{
	int i,j;
	n=read();
	for (i=1;i<=n;i++)
		a[i]=read(),f[i]=1000000000000000000ll;
	for (i=1;i<=n;i++)
		for (j=0;j<i;j++)
			f[i]=min(f[i],f[j]+1ll*(i-j)*(i-j-1)/2+a[i]);
	printf("%lld\n",f[n]);
	return 0;
}
显示 Gitment 评论