重考就我没改，退火还斜挂了，垫底了QWQ。
Solution
易得答案等于
$$
n \cdot \sum_{i=1}^n a_i^2-(\sum_{i=1}^na_i)^2
$$
然后不先推一波式子：
$$
\begin{aligned}
n \cdot \sum_{i=1}^n a_i^2-(\sum_{i=1}^na_i)^2 &= n \cdot \sum_{i=1}^n
(a_i-a_1)^2 - (\sum_{i=1}^n(a_i-a_1))^2 \\
&=n \cdot \sum_{i=1}^{n-1}(\sum_{j=1}^ib_j)^2-(\sum_{i=1}^{n-1}\sum_{j=1}^ib_j)^2 \\
\vdots\\
&= \sum_{i=1}^{n-1}\cdot b_i^2\cdot i\cdot(n-i)+2\sum_{j=1}^{n-1}\sum_{k=j+1}^{n-1}b_j\cdot b_k \cdot (n-j)\cdot k
\end{aligned}
$$
其中$b_i=a_{i+1}-a_i$
从最后一个式子可以看出最优解时差分数组呈现单谷（本人并没有看出来）。
附：对于这种结论，个人认为还是在考场上先写个程序将小数据的最优解的情况算出来，然后再用眼睛去蹬比较好。
然后得到差分数组单谷这个性质之后我们思考这个问题的解决方案，本人技艺不精，写了不够优秀的模拟退火，可以得到$84pts$，理论上（当然也有人确实做到了）可以拿到$96pts-100pts$。
但是仔细思考之后我们发现，完全可以乱搞。
当然，最简单的做法还是$dp$。
首先我们将差分数组排序，定义$f_{ij}$表示填了差分数组前$i$个数，其和为$j$的最优答案。
之后分将这个数放在左边还是放在右边两种情况讨论即可，不难得出转移方程式：
$$
f_{i,j+\sum_{k=1}^ib[k]}=\min f_{i-1,j}+(\sum_{k=1}^ib[i])^2\\
f_{i,j+b[i]\times i}=\min f_{i-1,j}+i \times(\sum_{k=1}^ib[i])^2+2\times j\times b[i]
$$
最上面的是放在右边的情况。下面是放在左边的情况。
然后我们会发现这个玩也儿是$O(n^2V)$，比较令人难受，但是我们观察最后一档得不到的分，此时的差分数组会出现大量的$0$，这意味着我们无论将这些东西放在左边还是放在右边都没有意义，于是将其特判掉（从有意义的开始转移）。
于是复杂度就是$O(\min(n,a)\times na)$了。
空间有点开不下，滚动一下数组。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 10005, M = 1e6 + 5;
int n;
int a[N], b[N], cnt, c[N];
LL f[2][M], sum, tot;
int main()
{
read(n);
for(int i = 1;i <= n;i ++) read(a[i]);
sum = n * a[n] * 2;
for(int i = 1;i < n;i ++) b[i] = a[i + 1] - a[i];
sort(b + 1, b + n);
for(int i = 1;i < n;i ++) c[i] += c[i - 1] + b[i];
for(int i = 1;i < n;i ++)
if(b[i] != 0) break;
else cnt ++;
memset(f[(cnt + 1) & 1], 0x3f, sizeof(f[(cnt + 1) & 1]));
f[(cnt + 1) & 1][0] = 0;
for(int i = cnt + 1, id;i < n;i ++)
{
memset(f[i & 1 ^ 1], 0x3f, sizeof(f[i & 1 ^ 1]));
for(int j = 0;j <= sum;j ++)
{
if(f[i & 1][j] > 1e18) continue;
f[i & 1 ^ 1][j + c[i]] = min(f[i & 1 ^ 1][j + c[i]], f[i & 1][j] + c[i] * c[i]);
f[i & 1 ^ 1][j + b[i] * i] = min(f[i & 1 ^ 1][j + b[i] * i], f[i & 1][j] + b[i] * b[i] * i + 2 * b[i] * j);
}
}
LL ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 0;i <= sum;i ++)
if(f[n & 1][i] < 1e18) ans = min(ans, f[n & 1][i] * n - 1ll * i * i);
write(ans);
return 0;
}
|