【萌新题解】方差

好久没上线ACGO了，先切一道水题练练

---

本题是动态规划（DP）优化，内容掌握即可，我的过程可能有些繁琐，靠滚动数组优化了一下，内存128MB，总体来说比较水。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define MAXM 500005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double ld;
typedef pair<LL,int> pii;
const LL INF=0x3f3f3f3f3f3f;    
const int mod1=998244353;
const int mod2=1e9+7;
const int inv2=499122177;
const int jzm=233333333;
const int zero=100;
const int lim=200;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
    _T f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
    x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;} 
int n,a[MAXN],tot,b[MAXN],maxx;LL ans,dp[2][MAXM];
signed main(){
    read(n);for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<n;i++)b[++tot]=a[i+1]-a[i];
    sort(b+1,b+tot+1);int now=0,las=1,summ=0;
    memset(dp,0x3f,sizeof(dp));dp[0][0]=maxx=0;
    for(int i=1;i<=tot;i++)if(b[i]){
        swap(now,las);summ+=b[i];int tp=b[i]*b[i],tmp=maxx;
        for(int j=0;j<=tmp;j++){
            dp[now][j+summ]=min(dp[now][j+summ],dp[las][j]+1ll*summ*summ),
            dp[now][j+i*b[i]]=min(dp[now][j+i*b[i]],dp[las][j]+2ll*j*b[i]+1ll*i*tp),
            dp[las][j]=INF,maxx=max(maxx,max(j+summ,j+i*b[i]));
        }
    }
    ans=INF;
    for(int j=0;j<=maxx;j++)if(dp[now][j]<INF-1)
        ans=min(ans,1ll*n*dp[now][j]-1ll*j*j);
    printf("%lld\n",ans);
    return 0;
}

学习更多内容请加入我们,成为一位dalao,%%%(1221入)