POJ2796 Feel Good

http://poj.org/problem?id=2796

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;
}

 

 

全部评论

相关推荐

05-24 14:12
门头沟学院 Java
点赞 评论 收藏
分享
当初高考报计算机真是造大孽了啊!卷的飞起!哪都是计算机的人,考研,考公,找工作全他奶的计算机的人,太难了。国企也是。关键一届比一届卷,造大孽了!
_Lyrics_:因为计算机,没有体验到快乐的大学研究生时光,好不容易修完课程就要出去实习,看着别人专业可以一起搓麻将,游山玩水,而我却要自己一个人住在北上不到十平米的出租屋,每天两点一线
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务