洛谷P2132 小Z的队伍排列 题解
题目链接：P2132 小Z的队伍排列
题意：
cxy 想给班里的同学拍一张合影（
尤其是给妹纸拍），为此需要先让大家排好队伍。她希望大家站成 $k$ 排，并规定了每排的人数，保证每一排的人数都不多于后面一排的人数。这时 cxy 发现队伍看起来还是乱糟糟的，原因是大家的身高互不相同。于是，她希望排头对齐，每位同学都比自己正后方的同学以及排头方向的同学矮。
排完以后，善于思考的 cxy 还想知道一共有多少种排法。
例如，大家排成 $3$ 排，且从后往前每排分别是 $3,2,1$ 人，就有以下 $16$ 种排法（每个数代表将所有同学身高从高到低排序后该同学的排名）：
可是班里一共有 $n$ 个人，cxy 算不出来了，希望你帮帮她（
因为拍完还要去找npy贴贴）。输入格式：
第一行包含一个整数 k。
第二行包含 k 个整数，表示从后往前每排的人数。
输出格式：
一行，包含一个整数，表示队伍排列的方案数。
数据范围：
$1 \le k \le 5,~1 \le n \le 30$，方案数小于 $2^{32}$。
注意到 $k$ 很小，所以我们可以暴力地设 $f(a,b,c,d,e)$ 为每行的人数（从上到下）。
如果 $a,b,c,d,e$ 之间的大小关系不合法，那么 $f=0$ 。然后 dfs 转移一下就好了。
时间复杂度 $\mathcal{O}((n/k)^k)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())
int k,x[15],f[31][31][31][31][31];
int dfs(int a,int b,int c,int d,int e)
{
if(!a && !b && !c && !d && !e) return f[a][b][c][d][e] = 1;
int &r = f[a][b][c][d][e]; if(r) return r;
if(a > b) r += dfs(a-1, b, c, d, e);
if(b > c) r += dfs(a, b-1, c, d, e);
if(c > d) r += dfs(a, b, c-1, d, e);
if(d > e) r += dfs(a, b, c, d-1, e);
if(e > 0) r += dfs(a, b, c, d, e-1);
return r;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> k;
for(int i = 1; i <= k; i++) cin >> x[i];
dfs(x[1], x[2], x[3], x[4], x[5]);
cout << f[x[1]][x[2]][x[3]][x[4]][x[5]] << '\n';
return 0;
}
