题解 NOIP2021 方差

原题

我认为这道题非常困难 码量并不大 可是需要很多次思维跳跃

题意

题意概述：

给定非严格递增序列 \(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;
}