1911: [Apio2010]特別行動隊
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1684 Solved: 706
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4
-1 10 -20
2 2 3 4
Sample Output
9
HINT
這題是斜率優化第一題：)
總體來說
我們試圖把方程寫成f[i]重j和k轉移來哪個優
只與kjk與i有關
考慮到轉移時點的橫坐標是遞減的（A*s[i]） 所以維護凸殼各種輕松~
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (1000000+10)
long long sqr(long long x){return x*x;}
int n;
long long a[MAXN],A,B,C,s[MAXN],f[MAXN];
long long calc(long long i,long long j)
{
long long tmp=s[j]-s[i-1];
return A*sqr(tmp)+B*tmp+C;
}
struct node
{
long long x,y;
int no;
node(){}
node(int _no):no(_no),x(A*s[_no]),y(f[_no]+A*sqr(s[_no])-B*s[_no]){}
friend long double kk(node a,node b){return (long double)(b.y-a.y)/(b.x-a.x);}
}q[MAXN];
//friend long long operator*(node a,node b){return a.x*b.y-a.y*b.x;}
struct V
{
long long x,y;
V(node a,node b):x(b.x-a.x),y(b.y-a.y){}
friend long long operator*(V a,V b){return a.x*b.y-a.y*b.x;}
};
int main()
{
freopen("bzoj1911.in","r",stdin);
scanf("%d%lld%lld%lld",&n,&A,&B,&C);
s[0]=0;
For(i,n) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
scanf("%lld%lld%lld",&A,&B,&C);
f[0]=0,f[1]=calc(1,1);
int head=0,tail=1;
q[0]=node(0);
q[1]=node(1);
// cout<<calc(1,3)<<' '<<calc(1,2)<<' '<<calc(3,3)<<endl;
Fork(i,2,n)
{
long double k=2*s[i];
while (tail-head>0&&kk(q[head],q[head+1])<=k) head++;
// cout<<q[head].no<<' ';
f[i]=f[q[head].no]+calc(q[head].no+1,i);
while (tail-head>0&&V(q[tail-1],q[tail])*V(q[tail],node(i))<0) tail--;
q[++tail]=node(i);
}
cout<<f[n]<<endl;
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (1000000+10)
long long sqr(long long x){return x*x;}
int n;
long long a[MAXN],A,B,C,s[MAXN],f[MAXN];
long long calc(long long i,long long j)
{
long long tmp=s[j]-s[i-1];
return A*sqr(tmp)+B*tmp+C;
}
struct node
{
long long x,y;
int no;
node(){}
node(int _no):no(_no),x(A*s[_no]),y(f[_no]+A*sqr(s[_no])-B*s[_no]){}
friend long double kk(node a,node b){return (long double)(b.y-a.y)/(b.x-a.x);}
}q[MAXN];
//friend long long operator*(node a,node b){return a.x*b.y-a.y*b.x;}
struct V
{
long long x,y;
V(node a,node b):x(b.x-a.x),y(b.y-a.y){}
friend long long operator*(V a,V b){return a.x*b.y-a.y*b.x;}
};
int main()
{
freopen("bzoj1911.in","r",stdin);
scanf("%d%lld%lld%lld",&n,&A,&B,&C);
s[0]=0;
For(i,n) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
scanf("%lld%lld%lld",&A,&B,&C);
f[0]=0,f[1]=calc(1,1);
int head=0,tail=1;
q[0]=node(0);
q[1]=node(1);
// cout<<calc(1,3)<<' '<<calc(1,2)<<' '<<calc(3,3)<<endl;
Fork(i,2,n)
{
long double k=2*s[i];
while (tail-head>0&&kk(q[head],q[head+1])<=k) head++;
// cout<<q[head].no<<' ';
f[i]=f[q[head].no]+calc(q[head].no+1,i);
while (tail-head>0&&V(q[tail-1],q[tail])*V(q[tail],node(i))<0) tail--;
q[++tail]=node(i);
}
cout<<f[n]<<endl;
return 0;
}
