#include
#include
#include
typedef unsigned long hh;
void main()
{
clock_t start,finish;
start=clock();
ifstream infile("input.txt",ios::in);
ofstream outfile("output.txt",ios::out);
int n;
infile>>n;
int i=0,j=0;
hh *a=new hh[n];
hh *b=new hh[n];
for(i=0;i
infile>>a[n-1-i];
infile>>b[n-1-i];
}
hh **c=new hh*[n];
hh **cost=new hh*[n];
for(i=0;i
c[i]=new hh[n];
cost[i]=new hh[n];
}
int sum=0,v=0,p=0,s=0,u=0;
for(i=0;i
for(i=0;i
for(j=i+1;j
c[j][i]=c[j-1][i]+b[j];
}
}
for(i=0;i
sum=0;
for(i=0;i
for(j=i+1;j
cost[j][i]=cost[j-1][i]+a[j]*c[j][i];
}
}
for(i=n;i>1;i--)//这里设i和j为两个最优点且(i>j)
{
if(i
sum=cost[n-1][i]; //算出n到i的服务量
}
else
{
sum=0;
u=cost[n-3][0];
}
if(i>3) //求出i到0的服务量最小值,并留下记号
{
v=cost[i-3][0]; //设一初值,用于比较,v最后的结果是i到0的服务量最小值
for(j=i-2;j>0;j--)
{
p=cost[i-2][j]; //i到j的服务量
if(j>1)
{
s=cost[j-2][0]; //j到0的服务量
}
else
s=0;
if(p+s
v=p+s;
}
}
}
else
v=0;
if(sum+v u=sum+v;
else
cout<