我认为这道题非常困难 码量并不大 可是需要很多次思维跳跃
题意
题意概述：
给定非严格递增序列 \(a_{n}\) 可以进行若干次操作，求序列方差的最小值的\(n^2\)倍
方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2\)，其中 \(\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i\)。
操作的定义：选取一个位置 \(i\space (1<i<n)\) 使得 \(a_i=a_{i-1}-a_i+a_{i+1}\)
其中 \(n\leq 10^4,\in a_i\le600\)
思路
1.操作本质
一个十分奇怪的操作 操作是选一个数 然后变为两边数的和减去当前的数
举个例子：
\(a\space b\space c\space d\to a\space a+c-b\space c\space d\)
这个时候可以把操作丢到数轴上思考：
手推一推 不难发现是 \(b\) 到 \(a\) 和 \(c\) 的距离交换
换句话说，就是交换差分
就此 这就是操作本质
2.求值本质
方差最小值？考虑化简方差式子
令 \(s=\sum\limits_{i=1}^na_i\)
则 \(D=n\sum\limits_{i=1}^n(a_i-\frac{s}{n})^2\)
拆开 \(D=n\sum\limits_{i=1}^n{a_i}^2+s^2-2\times\sum\limits_{i=1}^na_i\times s\)
最后化简得 \(D=n\sum\limits_{i=1}^n{a_i}^2-(\sum\limits_{i=1}^na_i)^2\)
至此，化简完毕
3.问题性质
得到交换差分之后 我们要进行推导
由于第一个差分不可以交换 放到最后考虑即可
令 \(d_i=a_i-a_{i-1}\) 继续拆式子
这一段拆了很久 放上最后的结果
\(D=n\sum\limits_{i=1}^n{d_i}^2\times i\times (n-i)+2\sum\limits_{j=1}^n\sum\limits_{k=j+1}^nd_j\times d_k\times k\times (n-j)\)
这个式子有什么呢？因为 \(d_j\times d_k\)是不会变的 而 \(i\times(n-i)\) 和 \(k\times (n-j)\) 这类式子会在值域中间取到最大值 因此 得到最小值 必须使中间的值最小.
最难的一部分就在这里.
4.问题解决
弄清性质 容易考虑 dp 算法
将差分数组排序 枚举这个数放在前面或者后面
那么，状态是什么呢？
我们发现答案的贡献为
\(D=n\sum\limits_{i=1}^n{a_i}^2-(\sum\limits_{i=1}^na_i)^2\)
\(\sum\limits_{i=1}^n{a_i}^2\) 非常不好维护 考虑维护 \(\sum\limits_{i=1}^na_i\)
定义 \(f_{i,j}\) 表示考虑到 \(i\) 差分 目前所有 \(\in a_x\) 的和为 \(j\) 时 所有数的平方和最小
记录 \(s_i\) 表示 \(\sum\limits_{j=1}^id_j\)
考虑将一个状态转移出去 那么有
1.放到当前数组的后面 \(f_{i+1,j+s_i}\to f_{i,j}+{s_i}^2\)
2.放到当前数组的前面 \(f_{i+1,j+i\times d_i}\to f_{i,j}+i\times{d_i}^2+2\times j \times d_i\)
枚举状态 \(O(n^2V)\) 转移 \(O(1)\)
可以得到 80pts
5.问题优化
时间复杂度太高了
考虑减少枚举状态数 因为有很多状态是不会转移到的
使用剪枝优化即可满分
时间复杂度 \(O(nV\min(n,V))\)
其他问题
统计答案要记得把第一个数插到队头
记得 long long
可以使用滚动数组优化
Code
#include<bits/stdc++.h>
#define ll long long
#define N 10005
#define V 605
using namespace std;
ll n;
ll d[N],sum;
ll a[N],s[N];
ll f[2][V*N*2];
ll ans=4e18;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),
d[i-1]=a[i]-a[i-1];
sort(d+1,d+n);
for(int i=1;i<n;i++)
s[i]=s[i-1]+d[i];
fill(&f[0][0],&f[1][V*N*2-5],4e18);
f[1][0]=0;
sum=0;
for(ll i=1;i<n;i++)
{
int p=i&1;
for(ll j=0;j<=sum;j++)
{
//放右边
f[p^1][j+s[i]]=min(f[p^1][j+s[i]],f[p][j]+s[i]*s[i]);
if(f[p^1][j+s[i]]!=4e18) sum=max(sum,j+s[i]);
//左边
f[p^1][j+d[i]*i]=min(f[p^1][j+d[i]*i],f[p][j]+2*j*d[i]+i*d[i]*d[i]);
if(f[p^1][j+d[i]*i]!=4e18) sum=max(sum,j+d[i]*i);
}
for(int j=0;j<=sum;j++)
f[p][j]=4e18;
}
for(ll i=0;i<=sum;i++)
{
if(f[n&1][i]==4e18) continue;
ans=min(ans,1ll*n*(f[n&1][i]+2ll*i*a[1]+n*a[1]*a[1])-(i+a[1]*n)*(i+a[1]*n));
}
printf("%lld",ans);
return 0;
}