Liveddd's Blog

愛にできることはまだあるかい

LOJ#3566. 「NOIP2021」方差

其实感觉这题出的挺好的,来补一下。

首先题目中的操作 ai=ai1+ai+1ai ,就是交换相邻两个数的差分。相当于我们要对差分进行重排使方差最小。

化简一下答案的式子得到:

ans=ni=1nai2(i=1nai)2

我们考虑将答案化成差分形式,再研究其性质:

ans=ni=1nai2(i=1nai)2=ni=1n1(j=1idj)2(i=1n1j=1idj)2=ni=1n1j=1ik=1idjdk(i=1n1(ni)di)2=ni=1n1j=1n1(nmax(i,j))didji=1n1j=1n1(ni)(nj)didj=i=1n1(j=1n1(i+jmax(i,j))nij)didj=i=1n1j=1n1(min(i,j)nij)didj

简单考虑邻值交换就能够得到:最优情况下,差分数组呈现单谷。

于是有了单谷性质,我们考虑从小到大依次考虑差分数组中的元素,考虑将它放在左侧还是右侧。考虑最开始答案的式子,我们将 iai 记录进状态,设计 f(i,j) 表示前 i 个差分数组,iai=j 的答案。设 si=j=1idi。转移时,考虑放在首还是尾,容易得到:

f(i1,j)+2jdi+idi2f(i,j+idi)f(i1,j)+si2f(i,j+si)

最终答案为 ans=minxnf(n1,x)x2。直接做时间复杂度是 O(n2a) 的无法通过。加一个小优化,直接跳过 di=0 的元素,这些元素不会发生任何转移。于是时间复杂度变为 O(namin(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;
}

未找到相关的 Issues 进行评论

请联系 @KevinLive 初始化创建