M_sea

洛谷4995 跳跳!
Luogu吐槽我月赛凉了啊。。。NOIP吃枣药丸qwq分析贪心。每次选一个高的差最大的点跳过去即可。要开long ...
扫描右侧二维码阅读全文
04
2018/11

洛谷4995 跳跳!

Luogu

吐槽

我月赛凉了啊。。。

NOIP吃枣药丸qwq

分析

贪心。

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

要开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;
}
最后修改:2018 年 11 月 09 日 06 : 52 PM

发表评论

3 条评论

  1. 符拉迪沃斯托克

    大佬,这个证明显然啊。。。相当于从hi到hj再到hk(hi>hj>hk),一定有:hi->hk->hj优于hi->hj->hk啊。。。当然我可能错了。。。

    1. M_sea
  2. smy

    我似乎会证明(大雾

    然而考场不会贪心,滚粗了qwq