【题目描述】
有 N 个能量发射站排成一行，每个发射站i都有不相同的高度 Hi，并能向两边（当然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比它高的发射站接收。
显然每个发射站有可能接收 0 或 1 或 2 个其它发射站发来的能量，特别是为了安全，它受到的能量总和是我们很关心的。由于数据很多，请你帮助我们计算出接受了最多能量的发射站接受的能量是多少。
【数据范围】
1 <= N <= 50,000
1 <= hi <= 2,000,000,000
1 <= vi <= 10,000
【输入格式】
第1行： 一个整数 N
第2..N+1行：第 i+1 行有2个整数 Hi Vi，表示第i个发射站的高和发射的能量值。
【输出格式】
一行：一个发射站接收到的最大能量值。
【样例输入】
3
4 2
3 5
6 10
【样例输出】
7
蒟蒻表示还是不会
怎么办呢？
随机枚举信号塔求此塔的接收值+卡时
。。。。。。
然后居然又A了
RP已败光。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
int m;
int z,ans;
struct self{int x,y;}s[50555]; //high->x power->y
int a,b,c;
int tall,num;
bool flag[50555];void eixt()
{cout<<z<<'\n';
}void work(int i)
{ans=0;int a,b,lt,rt;lt=rt=0;for(a=i-1;a>=1;a--){if(s[a].x>=s[i].x)break;if(s[a].x>=lt){ans+=s[a].y;lt=s[a].x;}}for(b=i+1;b<=m;b++){if(s[b].x>=s[i].x)break;if(s[b].x>rt){ans+=s[b].y;rt=s[b].x;}}z=max(z,ans);
}int main()
{freopen("mooo.in","r",stdin);freopen("mooo.out","w",stdout);scanf("%d",&m);for(a=1;a<=m;a++){scanf("%d%d",&s[a].x,&s[a].y);if(s[a].x>tall){tall=s[a].x;num=a;}}flag[num]=1;work(num);while((double)clock()/CLOCKS_PER_SEC<=0.91){ans=0;a=(rand()+rand())%m+1;while(flag[a]){a=(rand()+rand())%m+1;if((double)clock()/CLOCKS_PER_SEC>=0.93){eixt();return 0;}}flag[a]=1;work(a);}eixt();return 0;
}
还要ORZ XPF大神
我们可以先考虑向左发射信号
再考虑向右发射信号
用一个栈维护i前(或后)的第一个比h[i]高的塔的编号
先考虑向左发射的情况
对于栈顶top对应的ht和wt
如果当前i站的hi=>ht则需要找到第一个比hi大的ht 需要top--
因为stack的push是从前向后的 所以第一个满足ht>hi的top肯定是i前面第一个比h大的站
l[stack[top]]+=s[i].w; 同时i进栈
如果当前i站的hi<ht 表示i前的最低高度大于hi t站可以接收到i的信号
此时只需将i进栈 l[stack[top]]+=s[i].w;
正着一遍 反着一遍 ans=max(ans,l[i]+r[i]);
#include<iostream>
#include<cstdio>
using namespace std;
const int lim=50555;
int stack[lim];
int top;int l[lim],r[lim];struct self{int h,w;}s[lim];
int m,a,b,c;void left()
{int a,b;top=1;stack[1]=1;for(a=2;a<=m;a++){if(s[stack[top]].h>s[a].h){l[stack[top]]+=s[a].w;top++;stack[top]=a;}else{while(s[stack[top]].h<=s[a].h&&top>0)top--;if(top>=1)l[stack[top]]+=s[a].w;top++;stack[top]=a;}}
}void right()
{int a,b;top=1;stack[1]=m;for(a=m-1;a>=1;a--){if(s[stack[top]].h>s[a].h){l[stack[top]]+=s[a].w;top++;stack[top]=a;}else{while(s[stack[top]].h<=s[a].h&&top>0)top--;if(top>=1)l[stack[top]]+=s[a].w;top++;stack[top]=a;}}
}void print()
{int a,ans=0;for(a=1;a<=m;a++)ans=max(ans,l[a]+r[a]);cout<<ans<<'\n';
}int main()
{freopen("mooo.in","r",stdin);freopen("mooo.out","w",stdout);scanf("%d",&m);for(a=1;a<=m;a++)scanf("%d%d",&s[a].h,&s[a].w);left();right();print();return 0;
}
