其实感觉这题出的挺好的，来补一下。
首先题目中的操作 $a_i’=a_{i-1}+a_{i+1}-a_i$ ，就是交换相邻两个数的差分。相当于我们要对差分进行重排使方差最小。
化简一下答案的式子得到：
我们考虑将答案化成差分形式，再研究其性质：
简单考虑邻值交换就能够得到：最优情况下，差分数组呈现单谷。
于是有了单谷性质，我们考虑从小到大依次考虑差分数组中的元素，考虑将它放在左侧还是右侧。考虑最开始答案的式子，我们将 $\sum_i a_i$ 记录进状态，设计 $f(i,j)$ 表示前 $i$ 个差分数组，$\sum_i a_i=j$ 的答案。设 $s_i=\sum_{j=1}^i d_i$。转移时，考虑放在首还是尾，容易得到：
最终答案为 $ans=\min_x {n\cdot f(n-1,x)-x^2}$。直接做时间复杂度是 $\mathcal O(n^2a)$ 的无法通过。加一个小优化，直接跳过 $d_i=0$ 的元素，这些元素不会发生任何转移。于是时间复杂度变为 $\mathcal O(na\min(n,a))$。
可以用滚动数组优化一下空间。
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10,INF=1e9;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,ans=INF;
int a[N],b[N],sum[N];
int p,f[2][N*60];
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<n;i++)
b[i]=a[i+1]-a[i];
sort(b+1,b+n);
int begin=0;
for(int i=1;i<n;i++)
if(!b[i])
begin++;
for(int i=1;i<n;i++)
sum[i]=sum[i-1]+b[i];
memset(f[p^1],0x3f,sizeof(f[p^1]));
f[p^1][0]=0;
for(int i=begin+1;i<n;i++)
{
memset(f[p],0x3f,sizeof(f[p]));
for(int j=0;j<=a[n]*n;j++)
{
f[p][j+sum[i]]=min(f[p][j+sum[i]],f[p^1][j]+sum[i]*sum[i]);
f[p][j+b[i]*i]=min(f[p][j+b[i]*i],f[p^1][j]+j*2*b[i]+b[i]*b[i]*i);
}
p^=1;
}
for(int i=0;i<=a[n]*(n-1);i++)
if(f[p^1][i]<INF)
ans=min(ans,n*f[p^1][i]-i*i);
printf("%d",ans);
return 0;
}
|