题解

笔者做的加强版
N<=1000000
和楼下的各位不同
楼上是我同桌
和我的代码差不多

核心在
递归预处理

dp是查找pos左边第一个高度比pos大的位置
dp2是查找pos右边第一个高度比pos大的位置

f[pos][0]数组存的是pos左边第一个高度比pos大的位置
f[pos][1]数组存的是pos右边第一个高度比pos大的位置

** Accepted**

状态 耗时 内存占用

#1 Accepted 2ms 332.0KiB
#2 Accepted 2ms 324.0KiB
#3 Accepted 2ms 340.0KiB
#4 Accepted 2ms 460.0KiB
#5 Accepted 2ms 336.0KiB
#6 Accepted 3ms 332.0KiB
#7 Accepted 12ms 840.0KiB
#8 Accepted 24ms 1.453MiB
#9 Accepted 26ms 1.566MiB
#10 Accepted 24ms 1.441MiB
代码

#include<cstdio>
#include<algorithm>

using namespace std;
struct io
{
    int h;
    int v;  
}data[1000002];
int n;
long long val[1000002];
int f[1000002][2];

int dp(int pos,int h)
{   if(pos==0)  return 0;
    if(data[pos].h>h) return pos;
    return dp(f[pos][0],h);
}
int dp2(int pos,int h)
{
    if(pos==0) return 0;
    if(data[pos].h>h) return pos;
    return dp2(f[pos][1],h);
}
int main()
{
//  freopen("station.in","r",stdin);
//  freopen("station.out","w",stdout);
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d %d",&data[i].h,&data[i].v);


    
    for(int i=1;i<=n;i++)
          f[i][0]= dp(i-1,data[i].h);
    for(int i=n;i>=1;i--)
          f[i][1]= dp2(i+1,data[i].h);
//上两个循环是递归预处理

    
    for(int i=1;i<=n;i++)//val[pos]是pos这个位置得到的能量
    {
    int a=f[i][0],b=f[i][1];
    if(a!=0) val[a]+=data[i].v; 
    if(b!=0) val[b]+=data[i].v;
    }
    

    long long ans=0;
    for(int i=1;i<=n;i++)//比较结果
        ans=max(val[i],ans);


    printf("%lld",ans);

    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
long long h[50007],v[50007];
int z[50007],y[50007];
long long tot[50007];
int ans=0;
int main(){
    int n;
    cin>>n;
    v[0]=0;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>v[i];
        z[i]=0,y[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=1;j--){
            if(h[j]>h[i]) {z[i]=j;break;}
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(h[j]>h[i]) {y[i]=j;break;}
        }
    }
    for(int i=1;i<=n;i++){
        tot[z[i]]+=v[i];
        tot[y[i]]+=v[i];
    }
    for(int i=1;i<=n;i++){
        if(tot[i]>=ans) ans=tot[i];
    }
    cout<<ans;
}

直接搜就好了

var n,i,l,ans:longint; num,p,h,v:array [0..1000001] of longint;

procedure put(x:longint);
var j:longint;
begin
j:=l;
while (h[p[j]]<=h[x]) and (j>=1) do
dec(j);
l:=j+1;
p[l]:=x;
end;

begin
readln(n);
for i:=1 to n do
read(h[i],v[i]);
p[1]:=1;
l:=1;
for i:=2 to n do
begin
put(i);
if p[1]<>i then num[p[l-1]]:=num[p[l-1]]+v[i];
end;
for i:=1 to n do p[i]:=0;
p[1]:=n;
l:=1;
for i:=n-1 downto 1 do
begin
put(i);
if (p[1]<>i) then num[p[l-1]]:=num[p[l-1]]+v[i];
end;
ans:=0;
for i:=1 to n do
if ans<num[i] then ans:=num[i];
writeln(ans);
end.

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
int f[1000001],h[1000001],v[1000001],hf[1000001],hb[1000001];
int n;
int main()
{
    scanf("%d",&n);
    h[0]=2000000001;h[n+1]=2000000001;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&h[i],&v[i]);
        int pos=i-1;
        while(h[pos]<=h[i])
        pos=hf[pos];
        hf[i]=pos;
    }
        for(int i=n;i>=1;i--)
    {
        int pos=i+1;
        while(h[pos]<=h[i])
        pos=hb[pos];
        hb[i]=pos;
    }
/**/for(int i=1;i<=n;i++)
    {
        f[hf[i]]+=v[i];
        f[hb[i]]+=v[i];
    }
    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        maxx=max(maxx,f[i]);
    }
    printf("%d",maxx);
    //printf("\n%lf",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

这道题代码没那么难，开两个表（hf【】和hb【】），分别存前面和后面离第i个最近的且大于i的高度的位置（其实代码还可以优化，maxx可以在打表时找，不过懒得想了）
~~纯粹的浪费空间节约时间~~

此题好像没有 Free Pascal 的题解！！！
没关系！！我来！！
测试数据 #0: Accepted, time = 15 ms, mem = 1596 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1596 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1596 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1596 KiB, score = 10
Accepted, time = 92 ms, mem = 1596 KiB, score = 100

以下是伪代码：

Pascal Code

type    int=longint;
var
        n,i,max,k:int;
        a,b,c,d:array[0..50001]of int;
begin
        readln(n);
        for i:=1 to n do readln(a[i],b[i]);
        k:=1; d[1]:=1;
        for i:=2 to n do
        begin
                if a[i]<=a[d[k]] then
                begin
                        inc(k);
                        d[k]:=i;
                end else
                begin
                        repeat
                                inc(c[i],b[d[k]]);
                                dec(k);
                        until   (k=0) or (a[d[k]]>=a[i]);
                        inc(k);
                        d[k]:=i;
                end;
        end;
        k:=1; d[1]:=n;
        for i:=n-1 downto 1 do
        begin
                if a[i]<=a[d[k]] then
                begin
                        inc(k);
                        d[k]:=i;
                end else
                begin
                        repeat
                                inc(c[i],b[d[k]]);
                                dec(k);
                        until   (k=0) or (a[d[k]]>=a[i]);
                        inc(k);
                        d[k]:=i;
                end;
        end;
        max:=0;
        for i:=1 to n do if c>max then max:=c;
        writeln(max);
end.

如果奇迹有颜色那么一定是**橙色！**

单调栈...orz楼下的线段树

单调栈

LX题目没啥问题吧.....题目copy**并能向两边（当然两端的只能向一边）同时发射信号强度值为 Vi 的信号**

题解

动态开点的权值线段树...什么都不会就会这个TAT
线段树维护高度区间的最大/最小值.这里的值是指塔的位置.
从左到右扫一遍,取区间[h[i],+∞]中的最大,并把自己的位置i插入到h[i]位置
从右到左扫一遍,同上方法类似,取最小并插入.
ORZ楼下两位.....线段树代码长不说.....还死慢死慢的....( 可能离散化会好点...? )

测试数据 #0: Accepted, time = 15 ms, mem = 64272 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 64268 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 64272 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 64272 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 64272 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 64268 KiB, score = 10

测试数据 #6: Accepted, time = 93 ms, mem = 64272 KiB, score = 10

测试数据 #7: Accepted, time = 187 ms, mem = 64272 KiB, score = 10

测试数据 #8: Accepted, time = 171 ms, mem = 64276 KiB, score = 10

测试数据 #9: Accepted, time = 171 ms, mem = 64272 KiB, score = 10

###block code

const int INF=2000000001;

//segment tree dynamic nodes
struct node;
node*nil;
struct node
{
int mx,mi;
node*l,*r;
void update()
{ mx=max(l->mx,r->mx),mi=min(l->mi,r->mi); }
}pool[4000000];
node*nt=pool;
node*newnode()
{
nt->mx=-INF; nt->mi=INF; nt->l=nt->r=nil;
return nt++;
}
node*root;

int cp,cv;
node* Change(node*x,int l,int r)
{
if(cp<l || r<cp) return x;
if(x==nil) x=newnode();
if(l==r) { x->mx=x->mi=cv; return x; }
int mid=l+(r-l)/2;
x->l=Change(x->l,l,mid);
x->r=Change(x->r,mid+1,r);
x->update();
return x;
}
void Insert(int h,int v)
{ cp=h; cv=v; root=Change(root,0,INF); }

int ql,qr;
int QueryMax(node*x,int l,int r)
{
if(qr<l || r<ql) return -INF;
if(ql<=l && r<=qr) return x->mx;
int mid=l+(r-l)/2;
return max(
QueryMax(x->l,l,mid),
QueryMax(x->r,mid+1,r));
}
int QueryMax(int a,int b)
{ ql=a; qr=b; return QueryMax(root,0,INF); }

int QueryMin(node*x,int l,int r)
{
if(qr<l || r<ql) return INF;
if(ql<=l && r<=qr) return x->mi;
int mid=l+(r-l)/2;
return min(
QueryMin(x->l,l,mid),
QueryMin(x->r,mid+1,r));
}
int QueryMin(int a,int b)
{ ql=a; qr=b; return QueryMin(root,0,INF); }

int n;
int h[100050];
int v[100050];
int g[100050];

int main()
{
nil=newnode();
nil->l=nil->r=nil;
nil->mx=-INF;
nil->mi=INF;
root=nil;

scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",h+i,v+i);

for(int i=0;i<n;i++)
{
int p=QueryMax(h[i],INF);
if(p!=-INF)
{
g[p]+=v[i];
}
Insert(h[i],i);
}

root=nil;
nt=pool+1;

for(int i=n-1;i>=0;i--)
{
int p=QueryMin(h[i],INF);
if(p!=INF)
{
g[p]+=v[i];
}
Insert(h[i],i);
}

int res=0;
for(int i=0;i<n;i++) res=max(res,g[i]);

printf("%d\n",res);

return 0;
}

这题……语文不好读不懂啊！一开始我当是在距离上绝对的最近一个才会发送，结果是左边最近的和右边最近的………让人失望了哦……
至于解法吗，下面的大神也说了，不过他的是不是log（n）我不是很确定。
本人的算法是o（n）的。简单点说是建立一个栈。放入一个点之前，先检查之前的元素，如果高度比当前这个放入的元素低，那么出栈，直到栈空了，或者前一个的元素高度比当前元素大为止。向前一个元素增加信号。信号用一个额外的数组储存。我用的是pay【】数组（可以无视掉哦）。从左向右加入栈处理一次。清空栈，从右向左处理一次，最后一个1 to n 的循环，找到pay数组中的最大值，输出就ac了。至于代码……太难看了就不发了

测试数据 #0: Accepted, time = 0 ms, mem = 1812 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1808 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1808 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1804 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1808 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1812 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1808 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1812 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1808 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1804 KiB, score = 10
先亮一下。
这里没有题解？
别急，我来发。
此题明显O(log(n))的算法，而且我记得以前类似的看到过，数据范围还要大。
于是我们不禁想到了最长不下降序列的O(log(n))的算法。
过程：先正着扫一遍。开一个数组记录一个递减序列（即向右发射的每个未被接受的信号），前缀和优化。遇到一个高度时用二分找到数组中位置并替换，然后给这个位置加能量。再反得扫一遍吧。
起初我WA了三个点。以为没开LONG LONG，改了后还是3个。后来发现初始化add[1]写成了add[n]。

BY JSB 绍兴一中万岁！
#include<stdio.h>
using namespace std;
long h[50001],p[50001],a[50001];
long long max,ans[50001],add[50001];
long n,i,k,put;
long erfen(long l,long r)
{
long mid;

if (l==r) return l;
mid=long((l+r)/2);
if (h[i]<a[mid]) return erfen(mid+1,r);
else return erfen(l,mid);
}
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld %ld",&h[i],&p[i]);
for (i=1;i<=n;i++) ans[i]=0;
a[1]=h[1];k=1;add[1]=p[1];
for (i=2;i<=n;i++)
if (h[i]<a[k])
{
k++;a[k]=h[i];
add[k]=add[k-1]+p[i];
}
else
{
put=erfen(1,k);
ans[i]+=add[k]-add[put-1];
k=put;a[k]=h[i];add[k]=add[k-1]+p[i];
}
a[1]=h[n];k=1;add[1]=p[n];
for (i=n-1;i>0;i--)
if (h[i]<a[k])
{
k++;a[k]=h[i];
add[k]=add[k-1]+p[i];
}
else
{
put=erfen(1,k);
ans[i]+=add[k]-add[put-1];
k=put;a[k]=h[i];add[k]=add[k-1]+p[i];
}
for (i=1;i<=n;i++)
if (ans[i]>max) max=ans[i];
printf("%ld",max);
return 0;
}