Luogu

分析

贪心。

每次选一个高的差最大的点跳过去即可。

要开long long

证明不会,以后补。

upd:听了月赛讲评,用排序不等式证救星了qwq

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int sqr(int a) { return a*a; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n;
int h[310];
int vis[310];
inline void solve() {
    int ans=0,now=0;
    for (re int i=1;i<=n;++i) {
        int pos=1,Max=0;
        for (re int j=1;j<=n;++j)
        if (!vis[j]&&abs(h[j]-h[now])>Max) Max=abs(h[j]-h[now]),pos=j;
        ans+=sqr(h[pos]-h[now]),now=pos,vis[pos]=1;
    }
    printf("%lld\n",ans);
}

mainint main() {
    n=read();
    for (re int i=1;i<=n;++i) h[i]=read();
    solve();
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 33 PM