传送门
短代码简单题。
题意简述：对于一个序列XXX，定义其两个伴随序列a,ba,ba,b，aia_iai表示以第iii个数结尾的最长上升子序列长度，bib_ibi表示以第iii个数开头的最长下降子序列长度，现在给出aaa序列，问bbb序列所有数加起来最大值是多少。
思路：首先发现bbb序列就是把这个序列反过来之后得到的X′X'X′的aaa序列，因此贪心证明一波可以发现：对于这个需要自己构造的原序列是较大的数越靠前越好
然后可以根据aaa序列建一些有向边来表示各个位置的大小关系。
考虑证明如下两个性质：
- 如果∃a,b\exist a,b∃a,b满足a<b,Aa=Aba<b,A_a=A_ba<b,Aa=Ab，那么Xa≥XbX_a\ge X_bXa≥Xb，证明显然，如果不满足那么Ab≥Aa+1A_b\ge A_a+1Ab≥Aa+1
- 如果∃a\exist a∃a满足Aa!=1A_a!=1Aa!=1那么之前一定有至少一个At=Aa−1A_t=A_a-1At=Aa−1，考虑到性质1可以知道令离aaa最近的一个ttt使得Xt<XaX_t<X_aXt<Xa，而之前的都不一定是最优的。
现在已经很清楚如何建边了，我们对于每一个AAA值记一个preprepre数组表示前一个AAA出现的位置。
现在对于每个位置iii。
- preAipre_{A_i}preAi有意义，就从preAipre_{A_i}preAi向自己连一条有向边。
- preAi−1pre_{A_i-1}preAi−1有意义，就从自己向preAi−1pre_{A_i-1}preAi−1连一条有向边。
这样相当于连出来了一个模糊的关系图。
然后考虑让关系更加精确。
我们将这个图拓扑排序排出来最后的大小关系，那么由于较大的数越靠前越好所以我们用堆来维护这个出队顺序，强制让编号小的先出队即可。
然后考试的时候太慌统计答案的时候写错了丢了一个AK（摔
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
ll ans=0;
vector<int>e[N];
int q[N],hd,tl,f[N],pre[N],du[N],n,tot=0,stk[N],mp[N];
priority_queue<int,vector<int>,greater<int> >S;
int main(){
memset(pre,-1,sizeof(pre)),n=read(),tot=n+1;
for(ri i=1,x;i<=n;++i){
x=read();
if(~pre[x])e[pre[x]].push_back(i),++du[i];
if(~pre[x-1])e[i].push_back(pre[x-1]),++du[pre[x-1]];
pre[x]=i;
}
for(ri i=1;i<=n;++i)if(!du[i])S.push(i);
while(!S.empty()){
int p=S.top();
f[p]=--tot,S.pop();
for(ri i=0,v;i<e[p].size();++i){
--du[v=e[p][i]];
if(!du[v])S.push(v);
}
}
reverse(f+1,f+n+1);
int len=0;
for(ri i=1,pos;i<=n;++i){
if(f[i]>mp[len])mp[++len]=f[i],pos=len;
else mp[pos=lower_bound(mp+1,mp+len+1,f[i])-mp]=f[i];
ans+=pos;
}
cout<<ans;
return 0;
}