[bzojnoip十連測]小P的單調序列——權值線段樹優化DP

Description

小P最近喜歡上了單調數列，因為他覺得單調的數列具有非常多優美的性質。 經過 小P複雜的數學推導，他計算出了一個單調增數列的藝術價值等于該數列中所有數的總 和。

并且以這個為基礎，小P還可以求出任意一個數列的藝術價值，它等于将這個數列 陰次劃分為若幹個極長單調區間(相鄰兩個單調區間的單調性必須不相同)後，每個單 調區間中元素總和的平均值。 比如對于數列 3

7 9 2 4 5，它将被劃分為[3 7 9] [2] [4 5]， 其藝術價值為(19 + 2 + 9)/3 = 10。 由于小P特殊的審美觀，他還要求劃分出的第一個單

調區間必須為單調增區間，也就是說，對于數列 10 9 8，它将被劃分為[10] [9 8]，而不

是[10 9 8]。

現在小P于裡有一個長度為n的序列{ai}，他想問你，這個序列的所有子序列中，藝

術價值最大的是哪個子序列，輸出其藝術價值。

注意:本題單調數列為嚴格單調，也就是說數列中的數必須嚴格上升或嚴格下降。

思路：

好像 O(n3) O ( n 3 ) 的DP挺容易想的，但是範圍給的1e5，過不去。

發現這是求平均值，設上升為 U U ，下降為DD，有一段序列為 UDUDU U D U D U ，假設它的平均值最優，我們把它劃分一下成 UD|UD|U U D | U D | U ,必定會有大于等于平均值的一段，是以上述形式不可能最優，在每一小段裡面，若 U>D U > D 則取 U U 比取UDUD更優，反之則不滿足條件，于是得出答案就隻會是一段上升或者一段上升加一段下降的形式。

然後就變成了合唱隊形了。。。至于優化，用權值線段樹降低成了 O(nlogn) O ( n log ⁡ n )

/*================================
 * Author : ylsoi
 * Problem : interval
 * Algorithm : DP_and_Segment_Tree
 * Time : 2018.5.22
 * ===============================*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
void File(){
    freopen("interval.in","r",stdin);
    freopen("interval.out","w",stdout);
}
template<typename T>bool chkmax(T &_,T __){return _<__ ? (_=__,) : ;}
template<typename T>bool chkmin(T &_,T __){return _>__ ? (_=__,) : ;}
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
#define MREP(i,x) for(register int i=beg[x];i;i=E[i].last)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define inf INT_MAX
const int maxn=+;
int va[maxn],n,num[maxn],cnt;
pair<ll,int>a[maxn];
ll dp[maxn][],ans0,ans1,Max[maxn][];
struct Segment_Tree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define lc rt<<1
#define rc rt<<1|1
    ll Max[maxn<<];
    void update(int rt,int l,int r,int pos,ll x){
        if(l==r)Max[rt]=x;
        else{
            if(pos<=mid)update(lson,pos,x);
            else update(rson,pos,x);
            Max[rt]=max(Max[lc],Max[rc]);
        }
    }
    ll query(int rt,int l,int r,int L,int R){
        if(L>R)return l;
        ll ret=l;
        if(L<=l && r<=R)return Max[rt];
        else{
            if(L<=mid)chkmax(ret,query(lson,L,R));
            if(R>=mid+)chkmax(ret,query(rson,L,R));
        }
        return ret;
    }
}T;
bool cmp(pair<ll,int> x,pair<ll,int> y){
    return x.first<y.first;
}
int main(){
    File();
    scanf("%d",&n);
    REP(i,,n){
        scanf("%d",&va[i]);
        a[i].first=va[i];
        a[i].second=i;
    }
    sort(a+,a+n+,cmp);
    REP(i,,n)
        num[a[i].second]=++cnt;
    REP(i,,n){
        dp[i][]=T.query(,,n,,num[i]-)+va[i];
        T.update(,,n,num[i],dp[i][]);
    }
    mem(T.Max);
    DREP(i,n,){
        dp[i][]=T.query(,,n,,num[i]-)+va[i];
        T.update(,,n,num[i],dp[i][]);
    }
    REP(i,,n)chkmax(dp[i][],dp[i-][]);
    DREP(i,n,)chkmax(dp[i][],dp[i+][]);
    REP(i,,n)chkmax(ans0,dp[i][]);
    REP(i,,n-)chkmax(ans1,dp[i][]+dp[i+][]);
    if(ans0*>ans1)printf("%.3lf\n",(double)ans0);
    else printf("%.3lf\n",(double)ans1/);
    return ;
}