POJ2796 Feel Good

Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of life.

A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.

Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.

Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.

题意：选择一个区间，使得区间和与区间最小值之积最大。

思路：如果枚举区间左右端点的话，显然超时，那么枚举每一个位置作为区间最小值，然后就是快速查询该位置可以作为某区间最小值的最大区间，方法就是由该位置向两边延伸。

我的做法：二分+RMQ。因为从某p位置向左/右延伸过程中区间最小值在遇到比p值更小的之前，区间min一直是p值，以后>=p值，满足单调性。区间最值用ST表O(1)查询。总时间复杂度O(nlogn)。加读入优化以后卡过2891ms

单调栈做法：维护一个单调递增栈。时间复杂度O(n)。运行时间1110ms

DP预处理做法：https://www.cnblogs.com/pealicx/p/6270632.html时间复杂度 O(n)。运行时间954ms

注意：ans初始化为-1，不能为0，否则，数据全0就gg了！

单调栈：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define maxn 100000+100
#define ll long long

ll n,a[maxn],sum[maxn],l[maxn],r[maxn],ans=-1,ansl,ansr;

int main()
{
	freopen("input.in","r",stdin);
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
	a[0]=a[n+1]=-1;
	stack<int> s;
	for(int i=1;i<=n+1;i++)
	{
		while(!s.empty()&&a[i]<a[s.top()])
		{
			r[s.top()]=i;
			s.pop();
		}
		s.push(i);
	}
	while(!s.empty())s.pop();
	for(int i=n;i>=0;i--)
	{
		while(!s.empty()&&a[i]<a[s.top()])
		{
			l[s.top()]=i;
			s.pop();
		}
		s.push(i);
	}
	for(int i=1;i<=n;i++)
	{
		int L=l[i]+1,R=r[i]-1;
		if(ans<a[i]*(sum[R]-sum[L-1]))
		{
			ans=a[i]*(sum[R]-sum[L-1]);
			ansl=L;ansr=R;
		}
	}
	cout<<ans<<"\n"<<ansl<<" "<<ansr<<"\n";
	return 0;
}

二分+RMQ：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100000+100
#define ll long long

int n,a[maxn],d[maxn][20],ansl,ansr;
ll s[maxn],ans=-1;

void RMQ_init()
{
	for(int i=1;i<=n;i++)d[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
		}
}
int RMQ(int l,int r)
{
	int k=0;
	while((1<<(k+1))<=r-l+1)k++;
	return min(d[l][k],d[r-(1<<k)+1][k]);
}

bool check(int m,int mini)
{
	return RMQ(min(m,mini),max(m,mini))==a[mini];
}

inline int read()    
{  
    int x=0,f=1;  
    char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}

int main()
{
//	freopen("input.in","r",stdin);
	n=read();
	for(ll i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+a[i];
	RMQ_init();
	for(int mini=1;mini<=n;mini++)
	{
		int l=1,r=mini,m,pos1,pos2;
		while(l<=r)
		{
			m=(l+r)/2;
			if(check(m,mini))pos1=m,r=m-1;
			else l=m+1;
		}
		l=mini,r=n;
		while(l<=r)
		{
			m=(l+r)/2;
			if(check(m,mini))pos2=m,l=m+1;
			else r=m-1;
		}
		if((s[pos2]-s[pos1-1])*a[mini]>ans)
		{	
			ans=(s[pos2]-s[pos1-1])*a[mini];
			ansl=pos1;ansr=pos2;
		}
	}
	cout<<ans<<"\n"<<ansl<<" "<<ansr<<"\n";
	return 0;
}