征途 bzoj 4518

征途

【问题描述】

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

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

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

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

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

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

【输入格式】

第一行两个数 n、m。

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

【输出格式】

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

【样例输入】

5 2
1 2 5 8 6

【样例输出】

【数据范围】

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

题解：

来推一下式子：

方差：(x₁ - aver)² + (x₂ - aver)²+ ... + (x_m - aver)² / m

然后题意要求乘m²

那么

　m×[(x₁ - aver)² + (x₂ - aver)²+ ... + (x_m - aver)²]

= m×[x_1² + x_{2^{2 + ... + x_m²}} - 2aver(x₁+ x₂+ ... + x_m) + m × aver²]

= m×(x_1² + x_{2^{2 + ... + x_m²}}) - 2sum²+ sum²(aver = sum / m)

= m×(x_1² + x_{2^{2 + ... + x_m²}}) - sum²

其实m和sum都为常量，那么只要考虑中间的平方和部分

设f[i][j]为分到点j且分成i段时每一段的平方和

转移方程即为：f[i][j] = min(f[i][j], f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k])); (k < j)

三方效率肯定过不了，看出这是一个斜率优化的裸题，那就可以虾搞蛋了~\(≧▽≦)/~

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 inline int Get()

 {

     int x = ;

     char c = getchar();

     while('' > c || c > '') c = getchar();

     while('' <= c && c <= '')

     {

         x = (x << ) + (x << ) + c - '';

         c = getchar();

     }

     return x;

 }

 int n, m;

 int t, w;

 int c[];

 int s[];

 long long aver;

 long long f[][];

 long long sum[];

 double Up(int x, int y, int i)

 {

     return f[i - ][x] + sum[x] * sum[x] - f[i - ][y] - sum[y] * sum[y];

 }

 double Down(int x, int y)

 {

     return (sum[x] - sum[y]) << ;

 }

 long long Dp(int i, int j, int x)

 {

     return f[i - ][x] + (sum[j] - sum[x]) * (sum[j] - sum[x]);

 }

 int main()

 {

     scanf("%d%d", &n, &m);

     for(int i = ; i <= m; ++i)

         for(int j = ; j <= n; ++j)

             f[i][j] = 214748364721474836LL;

     for(int i = ; i <= n; ++i)

     {

         scanf("%d", &c[i]);

         sum[i] = sum[i - ] + c[i];

         f[][i] = sum[i] * sum[i];

     }

     aver = sum[n];

     for(int i = ; i <= m; ++i)

     {

         t = , w = ;

         s[++w] = i - ;

         for(int j = i; j <= n; ++j)

         {

 /*

             for(int k = i - 1; k <= j; ++k)

             f[i][j] = min(f[i][j], f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k]));

 */

             while(t < w && Up(s[t], s[t + ], i) / Down(s[t], s[t + ]) <= sum[j]) ++t;

             f[i][j] = Dp(i, j, s[t]);

             while(t < w && Up(j, s[w], i) / Down(j, s[w]) <= Up(s[w], s[w - ], i) / Down(s[w], s[w - ])) --w;

             s[++w] = j;

         }

     }

     printf("%lld", (long long) m * f[m][n] - aver * aver);

 }

巴特西

征途 bzoj 4518

最新文章

热门文章