2
29
2016
0

【APIO2010】【bzoj1911】【斜率优化dp】特别行动队commando

1911: [Apio2010]特别行动队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 3342  Solved: 1514
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

Source


【分析】

移项时注意符号,本题a<0

不等式左边分母复杂了点,但整体也满足斜率的定义。

数形结合突然不是很清晰了,用常规分析方法吧:

slope(a,b)<s[i],ba

slope(a,b)>slope(b,c),分情况:

1)slope(b,c)<s[i],说明cb优,舍去b

2)slope(b,c)>=s[i]:说明bc

由于slope(a,b)>slope(b,c)

则有slope(a,b)>=s[i],说明ab优,舍去b


【代码】#include<cstdio>

#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define inf 1<<30
using namespace std;
typedef long long LL;
const int N=2000000;
int n,A,B,C,q[N];
LL x[N],s[N],f[N],l,r;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline double slop(int k,int j)
{
	return double(f[j]-f[k]+A*(s[j]*s[j]-s[k]*s[k])-B*(s[j]-s[k]))/
	double (2*A*(s[j]-s[k]));
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("bzoj1911.txt", "r", stdin);
	freopen("commando.txt", "w", stdout);
	#endif
	n=read();
	A=read();B=read();C=read();
	F(i,1,n){
		x[i]=read();
		s[i]=s[i-1]+x[i];
	}
	F(i,1,n){
		while(l<r && slop(q[l],q[l+1])<s[i]) l++;
		int t=q[l];
		f[i]=f[t]+A*(s[i]-s[t])*(s[i]-s[t])+B*(s[i]-s[t])+C;
		while(l<r && slop(q[r-1],q[r])>slop(q[r],i)) r--;
		q[++r]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

【反思】

time:15:34-15:48-15:55 17:59-19:07

连交好几发,脑袋都瓦特了..

1、斜率方程一定要算对再敲代码

2、函数命名为slope不靠谱

3>,<是分析出来的,不可随意取==

4dp过程有平方等操作,开LL!!

 

(在bsoj上一次AC,而且是第一..

Category: 动态规划 | Tags: 前缀和 动归优化 动态规划 斜率优化dp | Read Count: 175

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com