Print Article
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 4810 Accepted Submission(s): 1451
Problem Description
Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.
Input
There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.
Output
A single number, meaning the mininum cost to print the article.
Sample Input
5 5 5 9 5 7 5
Sample Output
230
第一次写斜率优化，代码很丑。
斜率优化模式为dp[i]=min(a[j]*b[i]+c[j])+d[i]
则 dp[i]=a[j]*b[i]+c[j]+d[i]
b[i]*a[j]+d[i]-dp[i]=c[j]
等价于 a*x + b =y
而(x,y)已处理，可用log(n) 求出b的最值
与模板是式子本题f[i]=min(f[j]-2*sum[j]*sum[i]+sum[j]^2)+sum[i]^2+m相符。
另外，表示凸包写的还是很不熟练。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 510000
#define INF 0x3f3f3f3f
//AC
int n,m;
int num[MAXN];
typedef long long qword;
qword f[MAXN];
qword sum[MAXN];
inline qword sqr(int x)
{
return x*x;
}
//f[i]=min(f[j]-2*sum[j]*sum[i]+sum[j]^2)+sum[i]^2+m
//f[i]=-2*sum[j]*sum[i] + f[j]+sum[j]^2 +sum[i]^2 + m
// -2*sum[i]*sum[j] + sum[i]^2-f[i]+m == -f[j]-sum[j]^2
struct Point
{
qword x,y;
void init(qword xx,qword yy)
{
x=xx;y=yy;
}
};
Point make_point (qword x,qword y)
{
Point ret;
ret.init(x,y);
return ret;
}
qword xmul(Point p1,Point p2,Point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
double get_k(Point p1,Point p2)
{
if (p1.x==p2.x)throw "error";
return (double)(p2.y-p1.y)/(p2.x-p1.x);
}
struct Convex_Hall
{
Point pl[MAXN];
double kk[MAXN];
int topl;
void clear()
{
topl=-;
} Convex_Hall()
{
topl=-;
}
void add_point(Point pp)
{
if (topl<)
{
pl[++topl]=pp;
if (topl==&&pl[topl].x==pl[topl-].x)
{
if (pl[topl].y<pl[topl-].y)
{
topl--;
return ;
}else
{
pl[topl--]=pp;
return ;
} }
if (topl==)
{
kk[topl-]=get_k(pl[topl-],pl[topl]);
}
return ;
}
while (topl>=&&xmul(pl[topl-],pl[topl],pp)>=)
{
topl--;
}
pl[++topl]=pp;
kk[topl-]=get_k(pl[topl-],pp);
}
void pm()
{
int i;
for(i=;i<=topl;i++)
{
printf("(%d,%d) ",pl[i].x,pl[i].y);
}
printf("\n");
}
double get_maxb(double k)
{
int l,r,mid;
if (topl==-)throw "Error";
if (topl==)return pl[].y-pl[].x*k;
if (k>kk[])return pl[].y-pl[].x*k;
if (k<kk[topl-])return pl[topl].y-pl[topl].x*k;
l=,r=topl;
while (l<r)
{
mid=(l+r)>>;
if (kk[mid-]>=k&&kk[mid]<=k)
{
return pl[mid].y-pl[mid].x*k;
}
if (kk[mid-]<k)
{
r=mid;
}else
{
l=mid;
}
}
}
}H; int main()
{
//freopen("input.txt","r",stdin);
int i;
while (~scanf("%d%d",&n,&m))
{
H.clear();
for (i=;i<=n;i++)
{
scanf("%d",&num[i]);
sum[i]=sum[i-]+num[i];
}
memset(f,INF,sizeof(f));
/* f[0]=0;
for (i=1;i<=n;i++)
{
for (j=0;j<i;j++)
{
if (f[j]>=INF)continue;
f[i]=min(f[i],f[j]+sqr(sum[i]-sum[j])+m);
}
}
for (i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
*/ f[]=;
H.add_point(make_point(sum[],-sum[]*sum[]-f[]));
double k,b;
for (i=;i<=n;i++)
{
k=-*sum[i];
b=H.get_maxb(k);
f[i]=sum[i]*sum[i]+m-ceil(b);
H.add_point(make_point(sum[i],-sum[i]*sum[i]-f[i]));
// cout<<f[i]<<" ";
}
cout<<f[n]<<endl;;
}
return ;
}