[SCU4441] Necklace [2015 Sichuan Province Contest Final F]

題意

N個數構成一個環，現在可以删除一些數，使得這個環可以分成連續的三部分：X部分：所有數不降；Y部分：僅含一個值為10000的數；Z部分：所有數不增。（X，Y中不含值為10000的數），值為10000的數不超過10個。求滿足條件的環中，剩餘數字的和最大值。

題解

枚舉值為10000的數。确定值為10000的數的位置後，将環變為以這個10000為兩端的一條鍊。枚舉斷點i，我們可以用動态規劃求出（1，i）的數的不增序列的最大和，同理求出(i,n)的不增序列的最大和。發現每個權值不超過10000，可以在動态規劃的過程中用樹狀數組優化轉移。

代碼

/****************************************\
* Author : ztx
* Title  : F - Necklace
* ALG    : dp + BIT
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
typedef double lf ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG =  ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
    while (ret=getchar() , ret<'!') ;
    while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
    ret[]=;while (CH=getchar() , CH<'!') ;
    while (ret[++ret[]]=CH,CH=getchar(),CH>'!') ;
    ret[ret[]+]=;
}

#include <cstring>

#define  maxn  100010LL
#define  max(a,b)  (a)>(b)?(a):(b)
#define  lb (p&(-p))

int n , ans ;
int a[maxn<<] , c[] , f[maxn<<] , right[maxn<<] , left[maxn<<] ;

inline int GetMax(int p) {
    int ret= ; for (;p;p-=lb) ret=max(ret,c[p]) ; return ret ;
}

inline void Insert(int p,int w) {
    for (;p<;p+=lb) c[p]=max(c[p],w) ;
}

int main() {
int i , j ;
 //   #define READ
    #ifdef  READ
        freopen("data.in" ,"r",stdin ) ;
        freopen("me.out","w",stdout) ;
    #endif
    while (scanf("%d", &n) != EOF) {
        ans = L ;
        Rep (i,,n)
            read(a[i]) , a[i+n] = a[i] ;
        Rep (i,,n)
            if (a[i] == ) {
                memset(right,,sizeof right) ;
                memset(c,,sizeof c) ;
                memset(f,,sizeof f) ;
                rep (j,i,i+n) {
                    if (a[j] != )
                        f[j] = GetMax(-a[j])+a[j] ,
                        Insert(-a[j],f[j]) ;
                    right[j] = max(right[j-],f[j]) ;
                }
                memset(left,,sizeof left) ;
                memset(c,,sizeof c) ;
                memset(f,,sizeof f) ;
                rev (j,i+n,i) {
                    if (a[j] != )
                        f[j] = GetMax(-a[j])+a[j] ,
                        Insert(-a[j],f[j]) ;
                    left[j] = max(left[j+],f[j]) ;
                }
                rep (j,i,i+n)
                    ans = max(ans,right[j]+left[j+]+) ;
            }
        printf("%d\n", ans) ;
    }
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return  ;
}