Description
Alice 和 Bob 发明了一个新的游戏。给定一个序列 \(\{x_0,x_1,…,x_{n-1}\}\)。Alice 得到一个序列 \(\{a_0,a_1,…,a_{n-1}\}\)，其中 \(a_i\) 表示以 \(x_i\) 结尾的最长上升子序列的长度；Bob 得到一个序列\(\{b_0,b_1,…,b_{n-1}\}\),其中 \(b_i\) 表示以 \(x_i\) 开头的最长下降子序列的长度。 Alice 的得分是序列 \(\{a_0,a_1,…,a_{n-1}\}\) 的和，Bob 的得分是 \(\{b_0,b_1,…,b_{n-1}\}\) 的和。
Solution
由于 \(x\) 中相同的元素没有贡献，因此我们钦定 \(x\) 是 \(1\sim n\) 的排列。
题目给出了 \(a\) 序列，要最大化 \(b\) 序列。那么我们可以根据 \(a\) 序列来约束 \(x\) 序列，从而得到最大的 \(b\) 序列。
对于 \(i<j\)，如果 \(a_i\ge a_j\)，则说明 \(x_i>x_j\)，反之则可以将 \(x_j\) 接在 \(x_i\) 后面。
如果 \(a_i+1=a_j\)，则至少有一个 \(i\) 满足 \(x_i<x_j\)。
那我们可以尝试用 \(\mathrm{dfs}\) 来解决这个问题。
对于每个 \(a_i\)，找到最靠近的 \(a_j\) 满足 \(a_j+1=a_i\)，连一条 \((i,j)\) 的边。
注意要使用前向星，因为前向星的特性就是后加入的边先遍历。
然后求出 \(\mathrm{dfs}\) 序，可以证明 \(\mathrm{dfs}\) 序就是 \(x\) 序列。
求出 \(x\) 序列后，可以用 \(\mathcal O(n\log n)\) 求出 \(b\) 序列。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define ll long long
using namespace std;
struct node
{
int to,next;
}a[N<<1];
int n,x,tot,cnt,len,t[N],head[N],dfn[N],b[N],c[N];
ll ans;
void add(int x,int y)
{
a[++tot].to=y;
a[tot].next=head[x];
head[x]=tot;
}
void dfs(int x,int fa)
{
dfn[x]=++cnt;
for (int i=head[x];i!=-1;i=a[i].next)
{
int v=a[i].to;
if (v==fa) continue;
dfs(v,x);
}
}
int main()
{
freopen("alice.in","r",stdin);
freopen("alice.out","w",stdout);
memset(head,-1,sizeof(head));
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d",&x);
add(t[x-1],i);add(i,t[x-1]);
t[x]=i;
}
dfs(0,-1);
for (int i=1;i<=n;++i)
--dfn[i];
for (int i=1;i<=n;++i)
b[i]=dfn[n-i+1];
len=0;
for (int i=1;i<=n;++i)
{
int l=1,r=len,mid;
while (l<=r)
{
mid=(l+r)>>1;
if (b[i]>c[mid]) l=mid+1;
else r=mid-1;
}
len=max(len,l);
c[l]=b[i];
ans=ans+(ll)l;
}
printf("%lld\n",ans);
return 0;
}