跳跳
以为是个最长路，结果是个贪心
高度排序，然后每次跳高度差最大的点即可
网上找了个证明，想法很好但是没说清楚，应该是这样的：
要证明每次跳高度差最大的点最优，那么证明其中一次就行了，那么证明第一次
不妨设\(0=h_0<h_1<\cdots<h_n\)，假设第一次跳到\(h_p\)最优
第一次跳到\(h_p\)，如果最后一次跳到\(h_n\)，把这个过程反过来，即
\(h_0\to h_p \to h_{x1}\to h_{x2} \to \cdots \to h_{xi}\to h_n\)变为\(h_0\to h_n \to h_{xi}\to h_{x(i-1)} \to \cdots \to h_{x1}\to h_p\)
两种跳法的差异仅在于第一跳，反过来后体力值增加\(-h_p^2+h_n^2\)当\(h_p<h_n\)时体力值不最优
所以第一次跳到\(h_n\)最优
另一种情况，最后一次没有跳到\(h_n\)，不妨设\(h_n\)之后跳到\(h_q\)
相同地进行反转操作：\(h_0\to h_p \to h_{x1}\to h_{x2} \to \cdots \to h_{xi}\to h_n\to h_q\to \cdots\)变为\(h_0\to h_n \to h_{xi}\to h_{x(i-1)} \to \cdots \to h_{x1}\to h_p\to h_q\to \cdots\)
体力值增加\(-[h_p^2+(h_n-h_q)^2]+[h_n^2+(h_p-h_q)^2]=2h_nh_q-2h_ph_q\)
当\(h_p<h_n\)时体力值不最优，即此种情况下第一次跳到\(h_n\)也是最优
综上，第一次跳到\(h_n\)总是最优，证毕
最后发现贪心、最长路都是对的，只不过要开long long
寄
最长路
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
int i=0,f=1; char ch=0;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') f=-1, ch=getchar();
while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
return i*f;
}
const int N=1e3+5;
int n,h[N],dis[N];
vector<int>G[N];
priority_queue<pair<int,int> >q;
bool vis[N];
void Dijkstra(){
q.push(make_pair(dis[0],0));
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=true;
for(int v=0;v<=n;++v){
if(u==v) continue;
int w=G[u][v];
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;
q.push(make_pair(dis[v],v));
}
}
}
}
signed main(){
// freopen("1.in","r",stdin);
n=in;
for(int i=1;i<=n;++i) h[i]=in;
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j){
int w=(h[i]-h[j])*(h[i]-h[j]);
G[i].push_back(w);
}
Dijkstra();
int ans=dis[1];
for(int i=1;i<=n;++i) ans=min(ans,dis[i]);
// for(int i=1;i<=n;++i) printf("%d ",dis[i]); puts("");
printf("%lld\n",ans);
return 0;
}
贪心的一种写法
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
int i=0,f=1; char ch=0;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') f=-1, ch=getchar();
while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
return i*f;
}
const int N=1e3+5;
int n,h[N],ans,now;
signed main(){
// freopen("1.in","r",stdin);
n=in;
for(int i=1;i<=n;++i) h[i]=in;
sort(h+1,h+n+1);
int l=1,r=n;
while(r-l>1){
ans+=(now-h[r])*(now-h[r]);
now=h[r];
ans+=(now-h[l])*(now-h[l]);
now=h[l];
--r, ++l;
}
if(r-l==0) ans+=(now-h[l])*(now-h[l]);
if(r-l==1) ans+=(now-h[r])*(now-h[r])+(h[r]-h[l])*(h[r]-h[l]);
printf("%lld\n",ans);
return 0;
}
贪心的另一种写法
#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
int i=0,f=1; char ch=0;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') f=-1, ch=getchar();
while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
return i*f;
}
const int N=1e3+5;
int n,h[N],ans,now;
int sqa(int x){return x*x;}
signed main(){
// freopen("1.in","r",stdin);
n=in;
for(int i=1;i<=n;++i) h[i]=in;
sort(h+1,h+n+1);
int l=0,r=n;
for(int i=1;i<=n;++i){
if(l==r) break;
ans+=sqa(h[l]-h[r]);
++l;
if(l==r) break;
ans+=sqa(h[l]-h[r]);
--r;
}
printf("%lld\n",ans);
return 0;
}