自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:24:57，当前版本为作者最后更新于2022-09-20 15:29:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接

前言

• 神仙 DP 题，建议评紫，考场上只能 $30$ 分暴力走人，本篇题解便分别讲解一下 $30$ 分和 $100$ 分的做法。（之所以不讲 $50$ 分，是因为它没有什么区分度，能想到这一步的人一般就能拿满了）

30 分做法

• 考虑枚举每一个可能序列，由于每一个新增元素只有放最左或放最右两种选择，所以一共只会有 $2^n$ 种不同序列，对于每一个序列，我们用 $n^2$ 统计最长严格上升子序列及其数量，就可以总体以 $O(2^nn^2)$ 的复杂度解决问题，由于其实跑不满这么多，所以可以通过前 $30$ 分。

• 枚举时有一个小技巧：我们可以用2进制从前到后枚举 $2$ 到 $n$ 号元素怎么放，如果其对应位上为 $0$，就代表当前元素放到左边，我们就将其放入一个栈中，否则将其放入一个队列中，而最终序列就是：依次从栈中取出元素加上一号元素加上依次从队列中取出元素，读者可以思考一下为什么是这样。

• 由于暴力比较简单，就不放代码了。

100 分做法

• 首先我们需要将原问题进行转化，这也是本题最难的地方。

• 具体来说，我们不可能对每一个可能序列都进行操作，因为单是枚举的时间我们都无法接受，那让我们思考一下，对于任意一个可能序列，它与给定序列有什么关系？如果你有着惊人的直觉，或许可以看出：每一个可能序列，都是由给定序列选择一个子序列沿一号元素“翻折”至左侧得到的。

• 这么说可能有些抽象，换种说法，就是从原序列中抽出一些数，将这些数顺次组成一个新序列，再翻转这个序列，拼接至最左侧得到的。（这一部分请读者仔细理解）

• 而有了这个结论，我们再回去看题就容易了许多：对于可能序列的一个最长严格上升子序列，一定是由原序列的一个严格下降子序列和一个严格上升子序列拼接而成的，当然需要满足的条件是前者的最大值严格小于后者的最小值且二者无交，我们发现这样并不好求，所以我们可以将前者新增一个元素：严格上升子序列的最小值。

• 这样转化之后，如果我们用 $dp1(i)$ 和 $dp2(i)$ 分别表示以 $i$ 为开始的最长严格上升和下降子序列，那答案便是 $\max(dp1(i)+dp2(i)-1)$，其中 $i$ 从 $1$ 取到 $n$。

• 那接下来的问题就是如何求方案数，首先如果最长严格上升和下降子序列的个数分别为 $cnt1(i)$ 和 $cnt2(i)$ ，那对于确定的 $i$，子序列的个数显然是 $cnt1(i) \times cnt2(i)$，我们用 $len$ 表示最长严格上升子序列长度（拼接后），这时我们来考虑其他元素怎么放：

1. $A_1$ 属于最长严格上升子序列（拼接后），那这时不在序列中的所有元素显然有翻过去和不翻过去两种选择，所以它们的选择有 $2^{n-len}$ 种。

2. $A_1$ 不属于最长严格上升子序列（拼接后），这时不在序列中的元素除了$A_1$ 都有两种选择，可别忘了对于拼接前两个子序列的接口（就是同时属于两个序列的那个元素），由于它不是 $A_1$,所以它可以跟着任何一个序列走，翻不翻都可以，所以方案还要 $\times 2$，所以也是 $2^{n-len}$ 种。

• 综上所述，对于确定的 $i$，方案数为:

• 最后便是如何快速求最长严格上升子序列，相信大家都会 $n^2$ 的做法，而树状数组优化也不难，这里就不细讲了。（注意不能用贪心加二分，因为那样不便于统计方案数）

• 放代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define lowbit(x) x&-x
const int N=2e5+10,mod=1e9+7;
int n,A[N];
LL ans1,ans2,dp1[N],dp2[N],cnt1[N],cnt2[N],fac[N];
vector<int> vec;
struct node
{
	int val;
	LL num;
	node()	{val=0,num=1;}
	inline void add(int x,LL y)
	{
		if(x>val)	val=x,num=y;
		else if(x==val)	num=(num+y)%mod;
	}
}C1[N],C2[N];
inline void insert(int x,int y,LL z,node C[])
{
	for(;x<=n+1;x+=lowbit(x))	C[x].add(y,z);
}
inline node query(int x,node C[])
{
	node res;
	for(;x;x-=lowbit(x))	res.add(C[x].val,C[x].num);
	res.num=res.val?res.num:1;
	return res;
}
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++)	fac[i]=fac[i-1]*2%mod;
	for(int i=1;i<=n;i++)	scanf("%d",&A[i]),vec.push_back(A[i]);
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(int i=1;i<=n;i++)	A[i]=lower_bound(vec.begin(),vec.end(),A[i])-vec.begin()+2;
	for(int i=n;i>=1;i--)
	{
		node up=query(n+1-A[i],C1),down=query(A[i]-1,C2);
		dp1[i]=up.val+1,cnt1[i]=up.num;;
		dp2[i]=down.val+1,cnt2[i]=down.num;
		insert(n+2-A[i],dp1[i],cnt1[i],C1);
		insert(A[i],dp2[i],cnt2[i],C2);
	}
	for(int i=1;i<=n;i++)	
	{
		int len=dp1[i]+dp2[i]-1;
		if(len>ans1)	ans1=len,ans2=cnt1[i]*cnt2[i]%mod*fac[n-len]%mod;
		else if(len==ans1)	ans2=(ans2+cnt1[i]*cnt2[i]%mod*fac[n-len]%mod)%mod;
	}
	printf("%lld %lld",ans1,ans2);
	return 0;	
} 

• 完结撒花~