HDU 5806 NanoApe Loves Sequence

链接：点击打开链接

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int data[100005];
int sub[100005];
int main(){
	int t,n;
	int max1,max2,max3;
	int left,right,now;
	__int64 result;
	cin>>t;
	while(t--){
		cin>>n;
		result=0;
		for(int i=1;i<=n;i++)
			scanf("%d",&data[i]);
		for(int i=1;i<=n-1;i++)
			sub[i]=abs(data[i+1]-data[i]);
		sort(sub+1,sub+n);
		//for(int i=1;i<=n-1;i++)
			//printf("%d%c",sub[i],i==n-1?'\n':' ');
		max1=sub[n-1];
		max2=sub[n-2];
		max3=sub[n-3];
		//printf("%d %d %d\n",max1,max2,max3);
		if(max1==abs(data[2]-data[1]))
			result+=max2;
		else
			result+=max1;
		if(max1==abs(data[n]-data[n-1]))
			result+=max2;
		else
			result+=max1;
		//printf("%d\n",result);
		for(int i=2;i<n;i++){
			now=abs(data[i+1]-data[i-1]);
			left=abs(data[i]-data[i-1]);
			right=abs(data[i+1]-data[i]);
			if(now>=max1)
				result+=now;
			else{
				if(left==max1){
					if(right==max2)
						result+=max(max3,now);
					else
						result+=max(max2,now);
				}
				else if(right==max1){
					if(left==max2)
						result+=max(max3,now);
					else
						result+=max(max2,now);
				}
				else
					result+=max1;
			}
			//printf("%d:%d %d %d %d\n",i,left,right,now,result);
		}
		printf("%I64d\n",result);
	}
	return 0;
}