[APIO 2010]特別行動隊(スロープ最適化dp)
【問題解】
s[i]=x[1]+x[2]+・・・+x[i]の場合:f[0]=0 f[i]=max{f[j]+zdl(s[i]-s[j])}(i>0,0<=j=f[k]+a*(s[k]-s[k])^2+b*(b*(b*(s[k]+b*(s[k]-s[k])s[i]-s[k])+c整理得:f[j]+a*s[j]^2-f[k]-a*s[k]^2>=(2*a*s[i]+b)*(s[j]-s[k])t[i]=f[i]+a*s[i]^2,mi=2*a*s[i]+bは、t[j]-t[k]>=m*(s[j]-s[k])s[i]が単調に増加し、jmi(傾きが大きく、後優)がj=mi(kはjより優れている)⊃m単調に減少する∧任意のt>iに対して、K(j,k)>=mt(kはjより優れている)を満たす場合、キューヘッダを削除することができる
【コード】
s[i]=x[1]+x[2]+・・・+x[i]の場合:f[0]=0 f[i]=max{f[j]+zdl(s[i]-s[j])}(i>0,0<=j
【コード】
#include<stdio.h>
#include<stdlib.h>
typedef long long LL;
LL s[1000005],f[1000005],y[1000005],q[1000005];
double K(int i,int j)
{
return (double)(y[i]-y[j])/(double)(s[i]-s[j]);
}
int main()
{
double m;
LL a,b,c;
int n,i,j,head=0,tail=1;
scanf("%d%lld%lld%lld",&n,&a,&b,&c);
for(i=1;i<=n;i++)
{
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
for(i=1;i<=n;i++)
{
m=(double)(2*a*s[i]+b);
while(tail-head>=2&&K(q[head],q[head+1])>m) head++;
f[i]=f[q[head]]+a*(s[i]-s[q[head]])*(s[i]-s[q[head]])+b*(s[i]-s[q[head]])+c;
y[i]=f[i]+a*s[i]*s[i];
while( tail-head>=2 && K( q[tail-2] , q[tail-1] ) < K( q[tail-1] , i ) ) tail--;
q[tail++]=i;
}
printf("%lld",f[n]);
return 0;
}