单调栈(笛卡尔树区间DP)

75 阅读 0 评论 50 点赞

我是靠谱客的博主糟糕大树，这篇文章主要介绍单调栈(笛卡尔树区间DP)，现在分享给大家，希望可以做个参考。

【转载】作者：GuxueAkioi

学习之用，为防丢失，故此转载，万望见谅，若有侵权，联系删除。

题意：一开始有一个长度为 n 的未知排列。给出一个序列 a，其中 a[i] 表示单调栈在第 i 个数入栈后的 size 大小，a[i] = -1 表示 size 大小未知，根据序列 a 输出可能的初始排列的方案数。答案对 1e9+7 取模。

规模：T组数据，T<=20，1<=n<=100。

分析：首先考虑没有-1的情况，根据单调栈的性质我们不难发现最右边的 size==1 的位置其实就是原排列中 1 的位置。将这个位置记为 mid。而找到以后会把原序列分成左右两部分，这两部分中左边的size不变，但是右边的size就要--，因为1已经确定位置了，所以后面能动的数就少了1。然后再到两边找 size==1 的位置分段。这样递归下去，形态就等同一个小根笛卡尔树。因为左右分开以后大小就独立了，所以我们可以从所有数中任选一些数分给左边/右边，方案数即为 C(size,mid-l)。因为分段1次就是O(n)，分n次，复杂度O(n^2)。

那么有-1又怎么办呢？其实是一样的，枚举所有的 -1，如果在 mid 左边就不可选，在 mid 右边就可选，然后暴力分段搜。为了保证复杂度，采用记搜，f[l][r][k] 表示区间 [l,r]，前面已经分了 k 次段，即我们要在 [l,r] 中找最右边的、大小为 k+1 的继续进行分段。这样定状态就已经可以保证唯一了。然后方案数就是 f[l][r][k]=f[l][mid-1][k]*f[mid+1][r][k+1]*C(r-l,mid-l)。每个状态转移要花 O(n) 的复杂度枚举，所以一共是 O(n^4) 的复杂度，但是因为枚举区间自带大概 1/2 常数，部分状态又转移不到，所以实测跑得飞快。可以对于每个区间 [l,r] 预处理出 mid ，常数大概可以再*1/2，就可以获得和 @nkxjlym 巨佬一样的飞快速度！

总结：发现笛卡尔树模型以后就是简单暴力记搜题，其实难度不大。

复制代码

#include<bits/stdc++.h>
using namespace std;
const int mo=1000000007;
int n,a[110];
long long f[110][110][110],C[110][110];
long long ddfs(int l,int r,int k)
{
	if(f[l][r][k]!=-1) return f[l][r][k];
	if(l>r) return f[l][r][k]=1;
	if(l==r) return f[l][r][k]=(a[l]==k||a[l]==-1);
	f[l][r][k]=0;
	int mid=0,len=r-l;
	for(int i=r;i>=l;i--)
		if(a[i]==k){mid=i;break;}
	if(!mid)
	{
		for(int i=r;i>=l;i--)
			if(a[i]==-1)
				(f[l][r][k]+=ddfs(l,i-1,k)*ddfs(i+1,r,k+1)%mo*C[len][r-i])%=mo;
	}
	else
	{
		for(int i=r;i>mid;i--)
			if(a[i]==-1)
				(f[l][r][k]+=ddfs(l,i-1,k)*ddfs(i+1,r,k+1)%mo*C[len][r-i])%=mo;
		(f[l][r][k]+=ddfs(l,mid-1,k)*ddfs(mid+1,r,k+1)%mo*C[len][r-mid])%=mo;
	}
	return f[l][r][k];
}
int main()
{
	C[0][0]=1;
	for(int i=1;i<=100;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(f,-1,sizeof(f));
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		printf("%lldn",ddfs(1,n,1));
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int mo=1000000007;
int n,a[110];
long long f[110][110][110],C[110][110];
long long ddfs(int l,int r,int k)
{
	if(f[l][r][k]!=-1) return f[l][r][k];
	if(l>r) return f[l][r][k]=1;
	if(l==r) return f[l][r][k]=(a[l]==k||a[l]==-1);
	f[l][r][k]=0;
	int mid=0,len=r-l;
	for(int i=r;i>=l;i--)
		if(a[i]==k){mid=i;break;}
	if(!mid)
	{
		for(int i=r;i>=l;i--)
			if(a[i]==-1)
				(f[l][r][k]+=ddfs(l,i-1,k)*ddfs(i+1,r,k+1)%mo*C[len][r-i])%=mo;
	}
	else
	{
		for(int i=r;i>mid;i--)
			if(a[i]==-1)
				(f[l][r][k]+=ddfs(l,i-1,k)*ddfs(i+1,r,k+1)%mo*C[len][r-i])%=mo;
		(f[l][r][k]+=ddfs(l,mid-1,k)*ddfs(mid+1,r,k+1)%mo*C[len][r-mid])%=mo;
	}
	return f[l][r][k];
}
int main()
{
	C[0][0]=1;
	for(int i=1;i<=100;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(f,-1,sizeof(f));
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		printf("%lldn",ddfs(1,n,1));
	}
	return 0;
}