1911: [Apio2010]特别行动队
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 4061 Solved: 1922
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
4
-1 10 -20
2 2 3 4
-1 10 -20
2 2 3 4
Sample Output
9
题解：
首先我们可以推出原始方程式：
f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)
sum[]为前缀和
接着开始变形：
j<k
f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])/(2*a*sum[j]-sum[k])<sum[i]
(方程太长，懒得一步一步推，直接把结果写上）
于是我们可以得到两条性质：
1:slope(j,k)<sum[i],j<k
1:slope(j,k)<sum[i],j<k
2:j<k<i slope(j,k)<slope(k,i) k一定不是最优解。
于是可以优化方程。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
const int N=1000005;
int n;
int a,b,c;
long long sum[N];
int k,j;
long long yu[N],f[N];
double slope(int y,int x)
{
return (double)(f[x]-f[y]+a*sum[x]*sum[x]-a*sum[y]*sum[y]+b*(sum[y]-sum[x]))/(double)(2.0*a*(sum[x]-sum[y]));
}
int main()
{
sum[0]=0;
scanf("%d",&n);
scanf("%d%d%d",&a,&b,&c);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
k=0;j=0;yu[0]=0;
for(int i=1;i<=n;i++)
{
while(k<j&&slope(yu[k],yu[k+1])<(double)sum[i]) k++;
int k2=yu[k];
f[i]=f[k2]+a*(sum[i]-sum[k2])*(sum[i]-sum[k2])+b*(sum[i]-sum[k2])+c;
while(k<j&&slope(yu[j-1],yu[j])>slope(yu[j],i)) j--;
yu[++j]=i;
}
printf("%lld\n",f[n]);
}
#include<cstdlib>
#include<cstring>
const int N=1000005;
int n;
int a,b,c;
long long sum[N];
int k,j;
long long yu[N],f[N];
double slope(int y,int x)
{
return (double)(f[x]-f[y]+a*sum[x]*sum[x]-a*sum[y]*sum[y]+b*(sum[y]-sum[x]))/(double)(2.0*a*(sum[x]-sum[y]));
}
int main()
{
sum[0]=0;
scanf("%d",&n);
scanf("%d%d%d",&a,&b,&c);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
k=0;j=0;yu[0]=0;
for(int i=1;i<=n;i++)
{
while(k<j&&slope(yu[k],yu[k+1])<(double)sum[i]) k++;
int k2=yu[k];
f[i]=f[k2]+a*(sum[i]-sum[k2])*(sum[i]-sum[k2])+b*(sum[i]-sum[k2])+c;
while(k<j&&slope(yu[j-1],yu[j])>slope(yu[j],i)) j--;
yu[++j]=i;
}
printf("%lld\n",f[n]);
}
![python扩展库numpy中函数meshgrid()的使用[当你想要两个for循环嵌套处理时,就该想到它]](https://img-blog.csdnimg.cn/acc029196b0341ed99dc75c704d3afa6.png)
