Poj 3250 Bad Hair Day + Poj 2796 Feel Good (单调栈)

深藏阁楼爱情的钟 2022-08-24 14:16 1阅读 0赞

**Poj 3250 Bad Hair Day**

题意：有 n 头牛头站成一列。每头牛有一定的高度，并且能看到其前面高度比它低的牛的头顶，直到被某头高度大于等于它的高度的牛所挡住。计算每头牛能看到的牛头顶的数量之和。

#include <cstdio>
    #include <stack>
    using namespace std;
    
    int main ()
    {
    	int n;
    	while (~scanf("%d",&n))
    	{
    	    stack<int> s;
            long long sum=0;
    	    int i,tmp;
    	    scanf("%d",&tmp);
    	    s.push(tmp);
    	    for (i=1;i<n;i++)
    	    {
    	        scanf("%d",&tmp);
    	        while (!s.empty() && tmp>=s.top())
                    s.pop();
                sum+=s.size();  //栈中每头牛能看到的都多1个
                s.push(tmp);
    	    }
    	    printf("%lld\n",sum);
        }
    	return 0;
    }

**Poj 2796 Feel Good**

题意：求一个区间，使这个区间的和与这个区间中最小的数的乘积值最大。

写了一个STL的栈TLE了……于是就没有用栈……  
单调栈写法 http://blog.csdn.net/alongela/article/details/8231870

#include <cstdio>
    
    const int N=100005;
    
    int n;
    int ls[N],re[N];
    __int64 data[N],sum[N];
    
    void Deal ()
    {//找出一个数左侧右侧比他大的范围
    	int i,j;
    	data[0]=data[n+1]=-1;
    	for (i=1;i<=n;i++)
    		for (j=i-1;;j=ls[j])
    			if (data[j]<data[i])
    			{
    				ls[i]=j;
    				break;
    			}
    	for (i=n;i>=1;i--)
    		for (j=i+1;;j=re[j])
    			if (data[j]<data[i])
    			{
    				re[i]=j;
    				break;
    			}
    }
    
    int main ()
    {
    	int i,ansl,ansr;
    	scanf("%d",&n);
    	for (i=1;i<=n;i++)
    	{
    		scanf("%I64d",&data[i]);
    		sum[i]=sum[i-1]+data[i];
    	}	
    	__int64 ans=-1;
    	Deal ();
    	for (i=1;i<=n;i++)
    		if (ans<data[i]*(sum[re[i]-1]-sum[ls[i]]))
    		{
    			ans=data[i]*(sum[re[i]-1]-sum[ls[i]]);
    			ansl=ls[i]+1;
    			ansr=re[i]-1;
    		}
    	printf("%I64d\n%d %d\n",ans,ansl,ansr);
    	return 0;
    }