洛谷题面

前置知识：CF1110E。

可以看看写的 \(\textbf{题解}\)。

题目大意

给定长度为 \(n\) 的非严格递增正整数数列 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。每次可以进行的操作是：任意选择一个正整数 \(1 \lt i \lt n\)，将 \(a_i\) 变为 \(a_{i - 1} + a_{i + 1} - a_i\)。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 \(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\)。

题目分析

前置知识中提到：

令 \(c\) 为差分数组，且 \(c_i=a_{i+1}-a_i(1\le i\lt n)\)。

则一次操作 \(a_i=a_{i-1}+a_{i+1}-a_i\) 等价于交换 \(c_i\) 和 \(c_{i+1}\)，那么问题转换为：

给出长度为 \(n\) 的序列，重组原序列的差分数组，将得到的差分数组再求出 \(a\) 数组。求 \(n^2\times\min\{\dfrac{1}{n}\sum\limits_{i=1}^{n}(a_i-\bar a)^2\}\)。

显然可以 \(\operatorname{O}(N!)\) 枚举。

---

有一个重要的性质：答案差分数组一定先递减再递增。

于是可以随机化乱搞，\(84\) 分到手。

---

理一理式子：

\[n^2\times \dfrac{1}{n}\sum\limits_{i=1}^{n}(a_i-\bar a)^2 \]

\[=n\times [(a_1-\bar a)^2+(a_2-\bar a)^2+\cdots+(a_n-\bar a)^2] \]

\[=n\times (a_1^2+a_2^2+\cdots+a_n^2+n\times {\bar a}^2-(2a_1\bar a+2a_2\bar a+\cdots+2a_n\bar a)) \]

\[=n\times[(a_1^2+a_2^2+\cdots+a_n^2)+n\times {\bar a}^2-2\bar a\times(a_1+a_2+\cdots+a_n)] \]

发现 \((a_1+a_2+\cdots+a_n)\) 就是 \(n\times\bar a\)，于是：

\[=n\times(\sum\limits_{i=1}^n a_i^2-n\times \bar a^2) \]

\[=n\times\sum\limits_{i=1}^n a_i^2-n^2\times\bar a^2 \]

由于 \(n^2\times \bar a^2\) 等于 \((n\times \bar a)^2\)，即 \((\sum\limits_{i=1}^n a_i)^2\)，故有：

\[=n\times\sum\limits_{i=1}^n a_i^2-(\sum\limits_{i=1}^n a_i)^2 \]

---

令 \(m=n-1\)，\(dp[i][j]\) 表示当前考虑了差分数组的前 \(i\) 个时的 \(\sum\limits_{i=1}^n a_i\)。

这样转移会很方便，因为我们要想让 \(a\) 数组满足先减再增的性质，故只需要从小到大排序，然后依次考虑放左边还是放右边就好了。

\(c_i\) 放在右边时：

令 \(now=\sum\limits_{j=1}^i c_j\)，则 \(a_i=now\)（差分的性质）。

方程为 \(dp[i][j]\gets dp[i-1][j-now]+now^2\)。

\(c_i\) 放在左边时：

\(a\) 数组中这 \(i\) 个数都会加上 \(c_i\)，总共加了 \(i\times c_i\)。此时平方和的变化量为

\[\sum\limits_{j=1}^i (a_j+c_i)^2-\sum\limits_{j=1}^i a_j^2 \]

\[=\sum\limits_{j=1}^i c_i^2+\sum\limits_{j=1}^i(2\times a_j\times c_i) \]

\[=2\times c_i\times \sum\limits_{j=1}^i a_j+\sum\limits_{j=1}^i c_i^2 \]

设此时（转移之前）\(dp\) 数组的第二个状态为 \(p\)。

\[=2\times c_i\times p+i\times c_i^2 \]

方程为 \(dp[i][j]\gets dp[i-1][j-i\times c_i]+2\times c_i\times (j-i\times c_i)+i\times c_i^2\)。

代码

//2021/12/4

//2021/12/6

//2021/12/7

#define _CRT_SECURE_NO_WARNINGS

#include 

#include 

#include //need "INT_MAX","INT_MIN"

#include 

#include 

#define int long long

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int INF=0x3f3f3f3f3f3f3f3f;

const int ma=500005;

int a[ma],b[ma];

int dp[2][ma];

int n,sum;

#undef int

int main(void)
{
	#define int long long

	n=read();
	
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	
	for(register int i=1;i=0)
			{
				dp[idx][j]=min(dp[idx][j],dp[idx^1ll][j-i*b[i]]+i*b[i]*b[i]+2*b[i]*(j-i*b[i]));
			}
			
			if(j-now>=0)
			{
				dp[idx][j]=min(dp[idx][j],dp[idx^1ll][j-now]+now*now);
			}
		}
	}
	
	int ans=INF;
	
	for(register int i=0;i<=sum;i++)
	{
		if(dp[idx][i]