[NOIP2021] 方差

· · 个人记录

记差分数组为 d_i，则操作 a_i 等价于 \text{swap}(d_i,d_{i+1})

全部加上一个数，方差不变，可以不管 d_1

令 s=\sum\limits_{i=1}^n a_i

答案为 n\sum\limits_{i=1}^n(a_i-\frac{s}{n})^2

n\sum\limits_{i=1}^n (a_i^2 + \frac{s^2}{n^2} - \frac{2a_is}{n}) n\sum\limits_{i=1}^n a_i^2+s^2-2s\sum\limits_{i=1}^na_i n\sum\limits_{i=1}^n a_i^2 -(\sum\limits_{i=1}^n a_i)^2 n\sum\limits_{i=1}^n (\sum\limits_{j=1}^i d_j)^2-\sum\limits_{i=1}^n \sum\limits_{j=1}^i d_j n\sum\limits_{i=1}^n (\sum\limits_{j=1}^i d_j)^2-\sum\limits_{i=1}^n d_i(n-i+1) n\sum\limits_{i=1}^n (\sum\limits_{j=1}^i d_j)^2-(\sum\limits_{i=1}^n a_i)^2

只能找性质了，可以发现 d_i 成单谷

那么从小到大排序，每次只能添加到序列的开头或结尾

设 dp_{i,x} 表示考虑前 i 小的 d_i，且 a_i 之和为 x 的答案

由于 d_i=0 无效，省去即可做到 \text{O}(nV^2)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[10001];
ll s=1e18,k,d[10001],dp[500001];
int main(){
    for(int i=1;i<=500000;i++) dp[i]=1e16;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),m=max(m,a[i]*n);
    for(int i=1;i<n;i++) d[i]=a[i+1]-a[i];
    sort(d+1,d+n);
    for(ll i=1;i<n;i++){
        if(!d[i]) continue;
        k+=d[i];
        for(ll j=m;j>=0;j--){
            if(j+k<=m) dp[j+k]=min(dp[j+k],dp[j]+k*k);
            if(j+i*d[i]<=m) dp[j+i*d[i]]=min(dp[j+i*d[i]],dp[j]+2*d[i]*j+i*d[i]*d[i]);
            dp[j]=1e16;
        }
    }
    for(ll i=0;i<=m;i++) s=min(s,n*dp[i]-i*i);
    printf("%lld",s);
    return 0;
}