[BJWC2017] 太空飞船-题解
Dengxy
·
·
题解
此题数据范围与题面不符，原题传送门。
Description
将一个环分为 t 部分，第 i 个部分长度为 s_i，所有部分的平均长度为 s_{avg} ，求 \min\{t^2\sum (s_i - s_{avg})^2\}.
Solution
设 t 个部分总长度为 sum_n，有 s_{avg} = \frac{sum_n}{t}
那么答案即为
t^2\sum (s_i - s_{avg})^2 = t^2\sum s_i^2 - t \times sum_n^2.
k = 2
此时就是将环分成两部分，使得前一部分刚好小于 s_{avg}即可。
k = 3
和 k = 2 的情况一样，换成三部分即可。但是由于不一定分出的结果是最好的，所以要处理边界，尝试将分割点左右移动，找最小值。
k > 3
由于 t,sum_n 为常数，所以答案只与每部分长度的平方和有关。
于是问题转化为：将一个数列分为 t 部分，最小化每部分的平方和。
令 dp_{i,j} 表示前 i 个数，分为 j 部分，用 sum_i 表示前 i 部分的前缀和，得出状态转移方程：
dp_{i,j} = \min\limits_{0<k<i}\{ dp_{k,j-1} + (sum_i - sum_k)^2\}
设 $i_1 < i_2 $ 且 $dp_{i_1,j} < dp_{i_2,j}$，所以：
$$
dp_{i_1,j-1} + (sum_i-sum_{i_1})^2 < dp_{i_2,j-1} + (sum_i-sum_{i_2})^2
$$
即：
$$
2 \times sum_i < \frac{dp_{i_2,j-1}+sum_{j_2}-(dp_{i_1,j-1}+sum_{j_1})}{sum_{j_2}-sum_{j_2}}
$$
令 $Y(x) = dp_{x,j-1}+sum_x,X(x)=sum_x,$则：
$$
\frac{Y(i_2)-Y(i_1)}{X(i_2)-X(i_1)} > 2 \times sum_i
$$
最后直接斜率优化即可，时间复杂度 $O(n^2k)$。
# Code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int n,t,ans = 0x3f3f3f3f3f3f3f3f;;
int l[N],a[N],s[N];
int x[N],y[N],Fun[N],head,tail;
int f[N][2];
double slope(int j1,int j2)
{
return 1.0 * (y[j2] - y[j1]) / (x[j2] - x[j1]);
}
void solve2()
{
for(int i = 1;i <= n;++ i)
s[i] = s[i-1] + l[i];
int tmp = s[n] >> 1,pos = 0;
int sum = 0;
for(int i = 1;i <= n;++ i)
{
while(sum < tmp)
{
pos = pos + 1 > n ? 1 : pos + 1;
sum += l[pos];
}
ans = min(ans,sum * sum + (s[n] - sum) * (s[n] - sum));
sum -= l[i];
}
printf("%lld\n",t * t * ans - t * s[n] * s[n]);
}
void solve3()
{
for(int i = 1;i <= n;++ i)
s[i] = s[i-1] + l[i];
int tmp = s[n] / 3;
int pos1 = 1,pos2 = 1,sum1 = 0,sum2 = 0;
for(int i = 1;i <= n;++ i)
{
while(sum1 < tmp)
{
if(pos1 < pos2) sum2 -= l[(pos1 - 1) % n + 1];
//由于涉及第二段减去第一段选择的长度，用取模代替滚动
sum1 += l[(pos1 - 1) % n + 1];
++ pos1;
}
pos2 = max(pos2,pos1);
// printf("sum2 after pos1:%lld ,pos2:%lld\n",sum2,pos2);
while(sum2 + l[(pos2 - 1) % n + 1] <= s[n] - sum1 - sum2 - l[(pos2 - 1) % n + 1])//使两边尽量均衡
{
sum2 += l[(pos2 - 1) % n + 1];
++ pos2;
}
int sum3 = s[n] - sum1 - sum2,sum4;
ans = min(ans,sum1 * sum1 + sum2 * sum2 + sum3 * sum3);
sum3 = sum2 + l[(pos2 - 1) % n + 1],sum4 = s[n] - sum1 - sum3;
ans = min(ans,sum1 * sum1 + sum3 * sum3 + sum4 * sum4);
// printf("%lld pos:%lld %lld len:%lld %lld %lld or %lld %lld %lld\n",i,pos1,pos2,sum1,sum2,s[n] - sum1 - sum2,sum1,sum3,sum4);
sum1 -= l[i];
}
printf("%lld\n",t * t * ans - t * s[n] * s[n]);
}
signed main()
{
scanf("%lld%lld",&n,&t);
for(int i = 1;i <= n;++ i)
scanf("%lld",&l[i]);
if(t == 2)
{
solve2();
return 0;
}
if(t == 3)
{
solve3();
return 0;
}
for(int pos = 1;pos <= n;++ pos)
{
int cnt = 0,p = 0;
for(int i = pos;i <= n;++ i)
a[++cnt] = l[i];
for(int i = 1;i < pos;++ i)
a[++cnt] = l[i];
s[0] = 0;
for(int i = 1;i <= n;++ i)
{
s[i] = s[i-1] + a[i];
f[i][p^1] = s[i] * s[i];
}
for(int j = 2;j <= t;++ j)
{
head = 1,tail = 1;
for(int i = 1;i <= n;++ i)
{
while(head < tail && slope(Fun[head],Fun[head+1]) <= 2 * s[i])
++ head;
int k = Fun[head];
f[i][p] = f[k][p^1] + (s[i] - s[k]) * (s[i] - s[k]);
x[i] = s[i];
y[i] = f[i][p^1] + s[i] * s[i];
while(head < tail && slope(Fun[tail-1],Fun[tail]) >= slope(Fun[tail],i))
-- tail;
//维护一个下凸包
Fun[++tail] = i;
}
p ^= 1;
}
ans = min(ans,f[n][p^1]);
}
printf("%lld\n",t * t * ans - t * s[n] * s[n]);
return 0;
}
```