[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  ;
}