SCU - 4441 环形dp+树状数组优化

Necklace

frog has nn gems arranged in a cycle, whose beautifulness are a1,a2,…,ana1,a2,…,an. She would like to remove some gems to make them into a beautiful necklace without changing their relative order.

Note that a beautiful necklace can be divided into 3 consecutive parts X,y,Z where

XX consists of gems with non-decreasing beautifulness,
yy is the only perfect gem. (A perfect gem is a gem whose beautifulness equals to 1000010000)
ZZ consists of gems with non-increasing beautifulness.

Find out the maximum total beautifulness of the remaining gems.

Input

The input consists of multiple tests. For each test:

The first line contains 1 integer n ( $1 \leq n \leq 1 0^{5}$ ). The second line contains nnintegers a1,a2,…,an a1,a2,…,an. ( $0 \leq a i \leq 1 0^{4}, 1 \leq n u m b e r <mtext> </mtext> o f <mtext> </mtext> p e r f e c t g e m s \leq 10$ ).

Output

For each test, write 11 integer which denotes the maximum total remaining beautifulness.

Sample Input

    6
    10000 3 2 4 2 3
    2
    10000 10000

Sample Output

    10010
    10000

题意：

N个数构成一个环，现在可以删除一些数，使得这个环可以分成连续的三部分：

X部分：所有数不降

Y部分：仅含一个值为10000的数

Z部分：所有数不增

思路：

大体思路就是枚举每个10000的点，再枚举中间的每个端点，求10000右边的非递增序列最大和，求10000左边的非递减序列最大和。但是我们可以把这个数组复制成原来的两倍，那么 $i d$ 的复制品 $i d + n$ 之间的就是环的其他部分，我们可以用树状数组求每个端点从左边开始的非递增序列最大和以及每个端点从右边开始向左边的非递增序列最大和,时间复杂度为O（nllogn）。最后O(n)枚举分裂点求最大即可

AC代码：

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int MAX=10000;
int vc[20],vt;//存储10000的下标
int fa[200110],fb[200110],VA[200100];
int bt[10010],n;
int lowbit(int k)
{
    return k&-k;
}
void modify(int k,int val)
{
    while(k<=MAX)
    {
        bt[k]=max(bt[k],val);
        k+=lowbit(k);
    }
}
int getmax(int k)
{
    int ans=0;
    while(k>0)
    {
        ans=max(ans,bt[k]);
        k-=lowbit(k);
    }
    return ans;
}
int solve(int id)//id作为项链中心 返回最大值
{
    fa[id]=0;
    mset(bt,0);
    for(int i=id+1; i<=id+n; ++i)
    {
        if(VA[i]==10000)
        {
            fa[i]=fa[i-1];
            continue;
        }
        int tmp=getmax(10000-VA[i]+1)+VA[i];//10000-VA[i]的作用是 Va[i]越大，其10000-VA[i]越小,我们找比VA[i]大的序列最大和 直接树状数组找前面比10000-VA[i]小的的sum最大值即可
        fa[i]=max(fa[i-1],tmp);
        modify(10000-VA[i]+1,tmp);
    }
    mset(bt,0);
    fb[id+n]=0;
    for(int i=id+n-1; i>=id; --i)
    {
        if(VA[i]==10000)
        {
            fb[i]=fb[i+1];
            continue;
        }
        int tmp=getmax(10000-VA[i]+1)+VA[i];
        fb[i]=max(fb[i+1],tmp);
        modify(10000-VA[i]+1,tmp);
    }
    int ans=0;
    for(int i=id; i<id+n; ++i)
        ans=max(ans,fa[i]+fb[i+1]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n)
    {
        vt=0;
        for(int i=0; i<n; ++i)
        {
            cin>>VA[i];
            VA[i+n]=VA[i];
            if(VA[i]==10000)
                vc[vt++]=i;
        }
        int ans=0;
        for(int i=0; i<vt; ++i)
            ans=max(ans,solve(vc[i]));
        cout<<ans+10000<<endl;
    }
    return 0;
}

超时代码：

环形左边递增右边递减，上下一翻就是左边递减右边递增，那么求的之后只需总左边求递增，从右边求递减即可。

按道理没错，两个求出来的结果应该是一样的。可我的超时(;´༎ຶД༎ຶ`)

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int MAX=10000;
int vc[20],vt;//存储10000的下标
int fa[200110],fb[200110],VA[200100];
int bt[10010],n;
int lowbit(int k)
{
    return k&-k;
}
void modify(int k,int val)
{
    while(k<=MAX)
    {
        bt[k]=max(bt[k],val);
        k+=lowbit(k);
    }
}
int getmax(int k)
{
    int ans=0;
    while(k>0)
    {
        ans=max(ans,bt[k]);
        k-=lowbit(k);
    }
    return ans;
}
int solve(int id)//id作为项链中心 返回最大值
{
    fa[id]=0;
    for(int i=1;i<=MAX;++i) bt[i]=0;
    for(int i=id+1; i<=id+n; ++i)
    {
        if(VA[i]==10000)
        {
            fa[i]=fa[i-1];
            continue;
        }
        int tmp=getmax(VA[i])+VA[i];
        fa[i]=max(fa[i-1],tmp);
        modify(VA[i],tmp);
    }
    for(int i=1;i<=MAX;++i) bt[i]=0;
    fb[id+n]=0;
    for(int i=id+n-1; i>=id; --i)
    {
        if(VA[i]==10000)
        {
            fb[i]=fb[i+1];
            continue;
        }
        int tmp=getmax(VA[i])+VA[i];
        fb[i]=max(fb[i+1],tmp);
        modify(VA[i],tmp);
    }
    int ans=0;
    for(int i=id; i<id+n; ++i)
        ans=max(ans,fa[i]+fb[i+1]);
    return ans;
}
int main()
{
    while(~scanf("%d",&n))
    {
        vt=0;
        for(int i=0; i<n; ++i)
        {
            scanf("%d",VA+i);
            VA[i+n]=VA[i];
            if(VA[i]==10000)
                vc[vt++]=i;
        }
        int ans=0;
        for(int i=0; i<vt; ++i)
        {
            ans=max(ans,solve(vc[i]));
        }
        printf("%d\n",ans+10000);
    }
    return 0;
}