[Sdoi2016]征途

4518: [Sdoi2016]征途

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1125 Solved: 623
[Submit][Status][Discuss]

Description

Pine开始了从S地到T地的征途。

从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。

Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。

Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

帮助Pine求出最小方差是多少。

设方差是v，可以证明，v×m^2是一个整数。为了避免精度误差，输出结果时输出v×m^2。

Input

第一行两个数 n、m。

第二行 n 个数，表示 n 段路的长度

Output

一个数，最小方差乘以 m^2 后的值

Sample Input

5 2
1 2 5 8 6

Sample Output

HINT

1≤n≤3000,保证从 S 到 T 的总路程不超过 30000

把m^2乘进去。

S=((X-x1)^2+(X-x2)^2+......+(X-xm)^2)*m

  =m(m*X^2-2*X*(x1+x2+...+xm)+(x1^2+x2^2+...+xm^2))

  =m(x1^2+x2^2+...+xm^2)-(x1+x2+x3+...+xm)^2

观察这个式子，只需要求得(x1^2+x2^2+...+xm^2)的最小值就可以了。

设f[i][j]代表走到i天，走了j段路的最小代价，

f[i][j]=max(f[i-1][k]+(s[j]-s[k])^2)。

s[j]代表前缀和。初值f[0][0]=0。

明显可以斜率优化。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #define maxn 3010
 8 #define LL long long 
 9 using namespace std;
10 LL s[maxn],f[maxn][maxn],q[maxn];
11 bool getx(int i,int x1,int x2,int x3){
12   return (-s[x2]*s[x2]-f[i-1][x2]+s[x1]*s[x1]+f[i-1][x1])*(2*s[x2]-2*s[x3])>
13     (-s[x3]*s[x3]-f[i-1][x3]+s[x2]*s[x2]+f[i-1][x2])*(2*s[x1]-2*s[x2]);
14 }
15 LL getans(int i,int j,int k){
16   return -2*s[j]*s[k]+s[k]*s[k]+f[i-1][k]+s[j]*s[j];
17 }
18 int main()
19 {
20   freopen("menci_journey.in","r",stdin);
21   freopen("menci_journey.out","w",stdout);
22   int n,m;
23   scanf("%d%d",&n,&m);
24   for(int i=1;i<=n;i++)
25     scanf("%lld",&s[i]),s[i]+=s[i-1];
26   memset(f,127,sizeof(f));
27   f[0][0]=0;
28   for(int i=1;i<=m;i++){
29     int head=0,tail=1;
30     for(int j=1;j<=n;j++){
31       while(head+2<=tail && getx(i,q[tail-2],q[tail-1],q[tail]))
32     q[tail-1]=q[tail],tail--;
33       while(head<tail && getans(i,j,q[head])>=getans(i,j,q[head+1])) head++;
34       f[i][j]=getans(i,j,q[head]);
35       q[++tail]=j;
36     }
37   }
38   /*for(int i=1;i<=m;i++)
39     for(int j=1;j<=n;j++)
40       for(int k=0;k<=j;k++)
41     f[i][j]=min(f[i][j],f[i-1][k]+(s[j]-s[k])*(s[j]-s[k]));*/
42   printf("%lld",f[m][n]*m-s[n]*s[n]);
43   return 0;
44 }