NKOJ 4043 (CQOI 2017) 老C的键盘 （树形DP）

发表于 |
字数统计: 1,192字 | 阅读时长 ≈ 6min

P4043老C的键盘
NKOJ4043-1
NKOJ4043-2
NKOJ4043-3

此题由于给出的字符串，很容易想到变成一颗树，于是容易想到树形DP。

注意到将1-n分配到一棵树的时候，数的具体值是没有意义的，因此每一次往下分都可以认为是将1-size的排列分到这颗子树上。

因此，为了计算方案数，我们需要确定根的取值，再确定将哪些数分到左子树上，另一些分到右子树上，然后组合数乘一下，再乘上左子树和右子树各自的DP值。

注意到题目给出的限制是关于儿子和父亲的大小关系，因此我们预处理时，可以处理出在子树中有多少个与根的大小关系确定的数，由此确定根的取值范围，然后枚举根的取值，再枚举分配到子树上有多少个小于根的数或大于根的数。

最后，此题的重点，注意到由于子树的根和我当前讨论的这棵树的根的大小关系是确定的，并且讨论时确定了有多少个数小于根，因此相当于在子树中去分配数的时候，子树的根的取值范围是被限定了的。
举个栗子，如果已知根的左儿子大于根，同时当前左子树分配了k个小于根的数，那么左儿子在左子树中分配数时显然只能取k+1 - size，因此我们需要增加一维用来限制根的取值。

总结一下，我们用$F[x][y]$来表示以x为根的子树，将1-size[x]这些数分配到子树上，并且x取y的方案数。

转移的时候，因为x的取值是定的，因此枚举将1到y-1这些数分k个给左子树，再用y+1到size补足，配合组合数，乘上左右子树的根的取值满足上面要求的dp值，注意转移的边界，同时需要用前缀和优化。具体转移方程太烦琐，可以参看代码。（个人为了图方便，DP方程是针对不同的大小关系分开写的）

最后，我觉得这个dp过程中取模居然会出现负数实在有毒。

代码：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 233
using namespace std;
string s;
ll mod=1000000007LL;
ll n,C[N][N],F[N][N],G[N][N],ty[N],ls[N],rs[N],lc[N],rc[N],Sma[N],Big[N],size[N];
void DFS(ll x)
{
	size[x]=1;
	if(ls[x])
	{
		DFS(ls[x]);
		size[x]+=size[ls[x]];
		if(ty[ls[x]]==-1)
		{
			Sma[x]+=1+Sma[ls[x]];
			lc[x]=1+Sma[ls[x]];
		}
		else
		{
			Big[x]+=1+Big[ls[x]];
			lc[x]=1+Big[ls[x]];
		}
	}
	if(rs[x])
	{
		DFS(rs[x]);
		size[x]+=size[rs[x]];
		if(ty[rs[x]]==-1)
		{
			Sma[x]+=1+Sma[rs[x]];
			rc[x]=1+Sma[rs[x]];
		}
		else
		{
			Big[x]+=1+Big[rs[x]];
			rc[x]=1+Big[rs[x]];
		}
	}
}
void DP(ll x,ll y)
{
	if(ls[x])DP(ls[x],size[ls[x]]);
	if(rs[x])DP(rs[x],size[rs[x]]);
	ll i,j,k,t,p,q,ans;
	for(k=Sma[x]+1;k<=y-Big[x];k++)
	{
		ans=0;
		if(!rs[x])ans=1;
		if(ty[ls[x]]==-1&&ty[rs[x]]==-1)
		{
			for(i=max(lc[x],size[ls[x]]-y+k);i<=size[ls[x]]&&i<=k-1-rc[x];i++)
			ans=(ans+G[ls[x]][i]*G[rs[x]][k-1-i]%mod*C[k-1][i]%mod*C[y-k][size[ls[x]]-i]%mod)%mod;
		}
		if(ty[ls[x]]==1&&ty[rs[x]]==1)
		{
			for(i=max(lc[x],size[ls[x]]-k+1);i<=size[ls[x]]&&i<=y-k-rc[x];i++)
			ans=(ans+(G[ls[x]][size[ls[x]]]-G[ls[x]][size[ls[x]]-i])*(G[rs[x]][size[rs[x]]]-G[rs[x]][size[rs[x]]-y+k+i])%mod*C[y-k][i]%mod*C[k-1][size[ls[x]]-i]%mod)%mod;
		}
		if(ty[ls[x]]==-1&&ty[rs[x]]==1)
		{
			for(i=max(lc[x],size[ls[x]]-y+k+rc[x]);i<=size[ls[x]]&&i<k;i++)
			ans=(ans+G[ls[x]][i]*(G[rs[x]][size[rs[x]]]-G[rs[x]][k-i-1])%mod*C[k-1][i]%mod*C[y-k][size[ls[x]]-i]%mod)%mod;
		}
		F[x][k]=ans;
	}
	for(i=1;i<=y;i++)G[x][i]=(G[x][i-1]+F[x][i])%mod;
}
int main()
{
	ll i,j;
	scanf("%lld",&n);cin>>s;s="  "+s;
	for(i=0;i<=n;i++)C[i][0]=1;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(i=2;i<=n;i++)
	{
		if(s[i]=='<')ty[i]=1;
		else ty[i]=-1;
		if(ls[i/2])rs[i/2]=i;
		else ls[i/2]=i;
	}
	for(i=1;i<=n;i++)if(ls[i]&&rs[i]&&ty[ls[i]]>ty[rs[i]])swap(ls[i],rs[i]);
	DFS(1);DP(1,size[1]);
	cout<<(G[1][n]+mod)%mod;
}