p4995解题报告

· · 题解

题目传送门 link 。

推荐个人博客内食用，效果更佳哦。

如果将本题改为最小花费，相信大家都知道按顺序跳就可以了，而最大花费也就刚好与其相反，只要在最后一个没跳过的石头和第一个没跳过的石头之间反复横跳就行了。

接着，我们要有一个准确的证明。

首先排序一下，我们便能得到一个单调递增的数组。设这个数组为 a 数组，则 0=a_0<a_1<a_2<……<a_n。

这里我们使用反证法，证明比前面所说的更优的方案不存在。

假设 n 为 3，则前面所说的方案为：123，132，213，231，321，312。（为了省略文字，此处的 12 等意味着从 1 号砖跳到 2 号砖）

对于方案一：他就是最小值，所以肯定小于方案六。

对于方案二： 13 相等抵消。

而 23+01=a_1^2+a_2^2+a_3^2-2a_2a_3，03+12=a_1^2+a_2^2+a_3^3-2a_1a_2。

由于数组单调递增，所以 a1<a3，所以 2a_2a_3>2a_1a_2，即左式小于右式。

对于方案三：13,12 相等抵消，02 肯定小于 03。

对于方案四：13 相等抵消，接下去的过程同方案二。

对于方案五：03,12 相等抵消，23 明显小于 13。

综上，上面提出的方案便是最优方案。

可能有的同学要问了：你这只证明了一个 n=3 的特殊值，不具有普遍性,但是，对于一个常数 n，我可以把他分成若干份 3 和最后的 1，2。反复利用上述方法 3 个 3 个的合并，便可以证明出最终结果。

代码非常简短，如有疑惑可以看看注释

#include<bits/stdc++.h>
#define int long long//防止见祖宗的神器
using namespace std;
int n;
int a[310],ans;
signed main()
{
  ios::sync_with_stdio(0);//关闭同步，就可以放心的用cin,cout
  cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  sort(a+1,a+1+n,cmp);
  int t=0,w=n;//t：头，w：尾
  while(t<w)
  {
     ans+=(a[t]-a[w])*(a[t]-a[w]);//一次循环操作两次，也就是从最后跳到最前再跳到最后
     t++;
     ans+=(a[w]-a[t])*(a[w]-a[t]);
     w--;
  }
  cout<<ans;
  return 0;
}

完结撒花！