列表

详情

NC15815. Neat Tree

描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.

There is a row of trees along the East-9 Road which consists of N trees. Now that we know the height of each tree, the gardeners of HUST want to know the super-neatness of this row of trees. The neatness of a sequence of trees is defined as the difference between the maximum height and minimum height in this sequence. The super-neatness of this sequence of trees is defined as the sum of neatness of all continous subsequences of the trees.

Multiple cases please process until the end of input. There are at most 100 test cases.

输入描述

For each case:
The first line contains an integer N represents the number of
trees.
The next line n positive integers followed, in which hi represent the
height of the tree i. 

输出描述

For each test case, output a integer in a single line which represents the super-neatness of the row
of trees.

示例1

输入: 

3
1 3 1
4
1 2 3 4

输出: 

6
10

说明:

As for the first case, the super-neatness of the row of trees [1, 3, 1] is 6, because there are 6 different subsequence of this row of trees: [1] (from index 0 to index 0), neatness is 0; [1, 3] (from index 0 to index 1), neatness is 2; [1, 3, 1] (from index 0 to index 2), neatness is 2; [3] (from index 1 to index 1), neatness is 0; [3, 1] (from index 1 to index 2), neatness is 2; [1] (from index 2 to index 2), neatness is 0.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 611ms, 内存消耗: 28548K, 提交时间: 2019-08-16 10:37:13 

#include<iostream>
#include<stack>
using namespace std;
const int INF=0x3f3f3f3f;
int n;
int a[1000010];
int ll,rr;
long long f()
{
	stack<long long> s;
    long long ans = 0;
    a[n] = INF;
    for(int i=0; i<=n; i++)
	{
        while(!s.empty()&&a[s.top()] < a[i])
		{
            long long cur = s.top();
            s.pop();
            ll = s.empty()?0:s.top()+1;
            rr = i-1;
            long long tmp = (cur-ll)*(rr-cur);
            ans += a[cur]*( (rr-ll) + tmp );
        }
        s.push(i);
    }
    return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i;
	while (cin>>n)
	{
		for (i=0;i<n;i++)
			cin>>a[i];
		long long ans=f();
		for (i=0;i<n;i++)
			a[i]=-a[i];
        ans+=f();
        cout<<ans<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1153ms, 内存消耗: 12168K, 提交时间: 2020-06-22 11:42:36 

#include<bits/stdc++.h>
using namespace std;
const int mx=1e6+5;
int n,h[mx],l[mx],r[mx];
long long ans;
void fun(){
	for(int i=1,j=1;i<=n;j=++i){
		while(j>1&&h[j-1]<=h[i])j=l[j-1];
		l[i]=j;
	}
	for(int i=n,j=n;i;j=--i){
		while(j<n&&h[j+1]<h[i])j=r[j+1];
		r[i]=j;
	}
	for(int i=1;i<=n;++i)
		ans+=h[i]*(r[i]-l[i]+1ll*(r[i]-i)*(i-l[i]));
}
int main(){
	while(scanf("%d",&n)!=EOF){ans=0;
		for(int i=1;i<=n;++i)scanf("%d",h+i);
		fun();
		for(int i=1;i<=n;++i)h[i]=-h[i];
		fun();
		printf("%lld\n",ans);
	}
}

上一题

© 2025 nowcoder.com