Ryan_<

Description

Input

Output

Sample Input

Sample Output

HINT

Source

【分析】

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

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

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

若slope(a,b)<s[i],则b比a优

若slope(a,b)>slope(b,c),分情况：

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

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

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

则有slope(a,b)>=s[i],说明a比b优，舍去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、>,<是分析出来的，不可随意取==

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

（在bsoj上一次AC，而且是第一..）