【UVA1638】杆子的排列

题面

有高为 1， 2， …， n 的 n 根杆子排成一排， 从左向右能看到 L 根， 从右向左能看到 R 根。求有多少种可能的排列方式。

分析

数据范围仅200，本来是往组合数学方面想的，看到了这个200就放弃了念头，果然是dp

定义dp[i][j][k]是用了高度为1~i的杆子，从左边能看到j个，从右边能看到k个

如果从1转移到n很困难，因为放一个高的杆子进去会造成很多的遮挡影响，是几乎不能维护的。于是考虑从n转移到1，即先放比较高的杆子

加上放好了2~n高度的杆子，再放高度为1的杆子仅有三种情况

1.放在最左边。仅仅是从左看能多看到一个 dp[i][j][k]+=dp[i-1][j-1][k]

2.放在最右边，同理

3.放在中间，一定会被挡住。i-1根杆子间有（i-2）个可以放置的空格，则dp[i][j][k]+=dp[i-1][j][k]*(i-2)。

其实这里i的定义已经发生了一点变化，但是状态转移是很容易理解的

为什么可以把i等效定义为i个，而不是1~i呢？其实这只需要代表是i根高度不同的杆子，2~i的杆子全部砍1，相对高度没有变，也就等效成了1~i-1的杆子

代码

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define ll long long
#define N 220
ll dp[N][N][N];
ll t,n,l,r;
int main()
{    
    dp[1][1][1]=1;
    for(ll i=2;i<=200;i++)
        for(ll j=1;j<=i;j++)
            for(ll k=1;k<=i-j+1;k++)
                dp[i][j][k]=(dp[i-1][j-1][k]+dp[i-1][j][k-1]+dp[i-1][j][k]*(i-2)%mod)%mod;
    scanf("%lld",&t);            
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&l,&r);
        printf("%lld
",dp[n][l][r]);
    }    
    return 0;
}