递推。
用f[n][l][r]表示n个柱子,从左面能看到l个,从右面能看到r个。
如果我们按照从小到大的顺序放置的话,放置最高的柱子后,大量状态都能递推到当前状态,很难写出递推式。
但是我们如果从小到大放置的话,高度为1的柱子放进去只会产生3种不同的情况。
1.最左面.2.中间。3.右面
在中间的哪里是无所谓的。
所以f[i][j][k]=f[i-1][j-1][k]+f[i-1][j][k-1]+(i-2)*f[i-1][l][r]。
边界条件 f[1][1][1]=1。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
const int maxn = 20 + 10; LL f[maxn][maxn][maxn];
int n=20,l,r; void init() {
f[1][1][1]=1;
for(int i=2;i<=n;i++) {
for(int l=1;l<=n;l++)
for(int r=1;r<=n;r++) {
if(l+r>i+1) break;
f[i][l][r]=f[i-1][l-1][r]+f[i-1][l][r-1]+f[i-1][l][r]*(i-2);
}
}
} int main() {
int T;
init();
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&l,&r);
printf("%lld\n",f[n][l][r]);
}
return 0;
}