题解

1 条题解

  • 1
    @ 2017-10-04 14:52:11

    如此弱鸡的一道题,我竟然写的是splay树,然而用的并不熟练,于是最后写挂了。无奈用了个二叉排序树。
    不过还是附上正解代码,类似单调栈的思路。
    #include<bits/stdc++.h>
    using namespace std;
    int n,s[50002],d[50002],ans[50002],ANS,a[50002],b[50002],r,i;
    int main()
    {
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    s[1]=a[1];d[1]=1;r=1;
    for(i=2;i<=n;i++)
    {
    while(r!=0&&a[i]>s[r]){ans[i]+=b[d[r]];r--;}
    r++;
    s[r]=a[i];
    d[r]=i;
    }
    s[1]=a[n];d[1]=n;r=1;
    for(i=n-1;i>=1;i--)
    {
    while(r!=0&&a[i]>s[r]){ans[i]+=b[d[r]];r--;}
    r++;
    s[r]=a[i];
    d[r]=i;
    }
    for(i=1;i<=n;i++)ANS=max(ANS,ans[i]);
    cout<<ANS;
    return 0;
    }

  • 1

信息

难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者