A - 地震预测

A - 地震预测

怀特先生是一名研究地震的科学家，最近他发现如果知道某一段时间内的地壳震动能量采样的最小波动值之和，可以有效地预测大地震的发生。

假设已知一段时间的n次地壳震动能量的采样值为a₁,a₂,…a_n，那么第i 次采样的最小波动值为min{|a_i-a_j| | in。

请编写一个程序计算这n次采样的最小波动值之和。

Input

本题有多组输入数据，你必须处理到EOF为止

输入数据第一行有一个数n(1<=n<=10⁵) ,表示采样的次数。

第二行有n个整数，表示n次地壳震动能量的采样值a₁,a₂,…a_n (0<=a_i<=10⁷ )。

Output

输出n次采样的最小波动值之和。

Sample Input

4
2 0 3 10

Sample Output

21
代码：

/* 求最长递增子序列和最长递减子序列。*/

#include
#include
using namespace std;
int main()
{int n;int a[105],b[105],c[105];scanf("%d",&n);for(int i=0; i){scanf("%d",&a[i]);b[i]=1;c[i]=1;}for(int i=1; i)for(int j=0; j){if(a[j]1>b[i])b[i]=b[j]+1;}for(int i=n-1; i>=0; i--)   //反向求for(int j=n-1; j>i; j--){if(a[j]1>c[i])c[i]=c[j]+1;}int ans=0;for(int i=0; i)if(a[i]>=130&&a[i]<=230)ans=max(ans,b[i]+c[i]);printf("%d\n",n-ans+1);return 0;
}

转载于:https://www.cnblogs.com/fenhong/p/6719683.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！