洛谷P2132 小Z的队伍排列 题解

题目链接：P2132 小Z的队伍排列

题意：

cxy 想给班里的同学拍一张合影（尤其是给妹纸拍），为此需要先让大家排好队伍。她希望大家站成 \(k\) 排，并规定了每排的人数，保证每一排的人数都不多于后面一排的人数。

这时 cxy 发现队伍看起来还是乱糟糟的，原因是大家的身高互不相同。于是，她希望排头对齐，每位同学都比自己正后方的同学以及排头方向的同学矮。

排完以后，善于思考的 cxy 还想知道一共有多少种排法。

例如，大家排成 \(3\) 排，且从后往前每排分别是 \(3,2,1\) 人，就有以下 \(16\) 种排法（每个数代表将所有同学身高从高到低排序后该同学的排名）：

\[ \begin{array}{llllllllllllllll} 123 & 123 & 124 & 124 & 125 & 125 & 126 & 126 & 134 & 134 & 135 & 135 & 136 & 136 & 145 & 146 \\ 45 & 46 & 35 & 36 & 34 & 36 & 34 & 35 & 25 & 26 & 24 & 26 & 24 & 25 & 26 & 25 \\ 6 & 5 & 6 & 5 & 6 & 4 & 5 & 4 & 6 & 5 & 6 & 4 & 5 & 4 & 3 & 3 \end{array} \] 可是班里一共有 \(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;
}