题意

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

 

solution:

数据范围仅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<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define mp make_pair
#define pb push_back
#define first fi
#define second se
#define pw(x) (1ll << (x))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define eps 1e-9
#define PIE acos(-1)
#define cl(a,b) memset(a,b,sizeof(a))
#define fastio ios::sync_with_stdio(false);cin.tie(0);
#define lson l , mid , ls
#define rson mid + 1 , r , rs
#define ls (rt<<1)
#define rs (ls|1)
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define freopen freopen("in.txt","r",stdin);
#define cfin ifstream cin("in.txt");
#define lowbit(x) (x&(-x))
#define sqr(a) a*a
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int, int>
#define dd(x) cout << #x << " = " << (x) << ", "
#define de(x) cout << #x << " = " << (x) << "\n"
#define endl "\n"
using namespace std;
//**********************************
ll dp[][][];//dp[i][j][k]表示i个棒子从左边能看到j个右边能看到k个的方案数
//**********************************
void Init()
{
dp[][][]=;
FOR(i,,)FOR(j,,i)FOR(k,,i-j+)dp[i][j][k]=dp[i-][j-][k]+dp[i-][j][k-]+dp[i-][j][k]*(i-);
}
//**********************************
int main()
{
Init();
int T;cin>>T;
while(T--){
int a,b,c;cin>>a>>b>>c;
cout<<dp[a][b][c]<<endl;
}
return ;
}
05-28 21:45