UVa 10128 - Queue
传送门
思路
一开始从排列组合考虑，想不出来。看了别人的题解。
假设从高到矮一个一个进去，当第i个人进去的时候，他有三种位置可以站
- 站队伍最前面。这时候从前面看的数目就多了一个。
- 站队伍最后面。这时候从后面看的数目就多了一个。
- 站队伍里面。空位随便选。
$dp[i][j][k]$表示总共i个人从前面看j个人从后面看k个人。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL dp[14][14][14];
LL DFS(int all, int h, int t)
{
LL &cur = dp[all][h][t];
if (h > all || t > all)
return cur = 0;
if (h == 0 || t == 0)
return cur = 0;
if (all == 1)
return cur = 1;
if (cur != -1)
return cur;
cur = 0;
cur = DFS(all - 1, h - 1, t) + DFS(all - 1, h, t - 1) + (all - 2) * DFS(all - 1, h, t);
return cur;
}
int main()
{
//freopen("input.txt", "r", stdin);
int T, i, j;
scanf("%d", &T);
while (T--)
{
memset(dp, -1, sizeof dp);
int all, h, t;
scanf("%d%d%d", &all, &h, &t);
printf("%lld\n", DFS(all, h, t));
}
return 0;
}