CSU 4441 Necklace (树状数组/LIS)

题目链接：传送门

题意：

给定一个循环序列，然后我们从中找出三个连续的子串，然后使得这三个的子串的和最大。

三个要求：

1）一个子串要连续非递减。

2）一个子串要连续非递增。

3）一个为10000.

分析：

对于一个包含10000的序列正着做一次LIS，然后再倒着做一次LIS，用树状数组维护使他们的和最大。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int M = 1e4+10;
int A[maxn],n;
int bit[M];
int R[maxn];

inline int lowbit(int x) {
    return x&(-x);
}

void modify(int pos,int val) {
    while(pos<=10000) {
        bit[pos]=max(bit[pos],val);
        pos+=lowbit(pos);
    }
}

int query(int pos) {
    int ans = 0;
    while(pos) {
        ans = max(ans,bit[pos]);
        pos-=lowbit(pos);
    }
    return ans;
}

void init() {
      memset(bit,0,sizeof(bit));
}

int calc(vector<int > &vc) {
    init();
    for(int i=0;i<vc.size();i++)
        vc[i]=10000-vc[i];
    for(int i=vc.size()-1;i>=0;i--){
        modify(vc[i],query(vc[i])+10000-vc[i]);
        R[i]=query(10000);
        cout<<vc[i]<<" "<<R[i]<<endl;
    }
    init();
    int ret=query(10000);
    for(int i=0;i<vc.size();i++){
        ret=max(ret,query(10000)+R[i]);
        modify(vc[i],query(vc[i])+10000-vc[i]);
    }
    return ret;
}

int solve() {
    int ret = 0;
    for(int i=n+1; i<=2*n; i++) {
        if(A[i]==10000) {
            vector<int > vc;
            for(int j=n-1;j>=1;j--){
                if(A[i-j]!=10000)
                    vc.push_back(A[i-j]);
            }
            ret = max(ret,10000+calc(vc));
        }
    }
    return ret;
}

int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++) {
            scanf("%d",A+i);
            A[i+n]=A[i];
        }
        printf("%d\n",solve());
    }
    return 0;
}
/***
6
10000 3 2 4 2 3
2
10000 10000
10
9990 9991 9992 9993 9994 9995 9996 9997 9998 10000
4
3 1 4 10000
**/