Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

Luogu P2132 小Z的队伍排列 解题报告

P2132 小Z的队伍排列

小Z想给班里的同学拍一张合影,为此需要先让大家排好队伍。他希望大家站成 $k$ 排,并规定了每排的人数,保证每一排的人数都不多于后面一排的人数。

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

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

解题思路:

线性 DP。

首先因为“保证每一排的人数都不多于后面一排的人数”且“每位同学都比自己正后方的同学以及排头方向的同学矮”,所以合法方案中每行每列的身高显然单调。

所以我们可以从高到低考虑每个学生所站的位置,这样搞的话,我们只要用一个$(a_1,a_2,a_3…a_n)$ 就能体现出已经处理的东西的轮廓。

而每次考虑一个学生的时候,为了保证单调性,我们只能将他放在满足人员未满并且 $a_i < a_{i-1}$ 或 $i = 1$ 的行中。

所以定义 $(a_1,a_2,a_3…a_n)$ 为阶段,这样就满足了动态规划问题的最优子结构性质,并且每安排一名新学生时候 $a_1,a_2,a_3…a_n$ 中总有一个会 $+1$,满足各个维度线性增长的原则,也就是线性 DP 了。

接下来,我们来设计状态转移方程,本题中的 $k \leq 5$,所以无脑设计

$f_{a_1,a_2,a_3,a_4,a_5}$表示每排从最左边起分别站了 $a_1,a_2,a_3,a_4,a_5$ 个人的方案数量

$f_{0,0,0,0,0} = 1$

目标:$f_{k_1,k_2,k_3,k_4,k_5}$

转移:

当 $i = 1$ 时,如果 $a_1 < k_1$,也就是人还没被放满时,$f_{a_1+1,a_2,a_3,a_4,a_5}+=f_{a_1,a_2,a_3,a_4,a_5}$

当 $i > 1$ 时,如果 $a_i < k_i \& a_i < a_{i-1}$,$f_{a_1,a_2+1,a_3,a_4,a_5}+=f_{a_1,a_2,a_3,a_4,a_5}$

(此处为当$i = 2$时,其他同理。)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <string>
#include <cmath>
#include <stack>
using namespace std;

#define ll long long
#define ri register int

char buf[1 << 20], *p1, *p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
ri v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const int INF = 0x3f3f3f3f;
const int N = 31;

ll f[N][N][N][N][N],n;
int a[N];

signed main() {
read(n);
for (int i = 1;i <= n;++i) read(a[i]);
f[0][0][0][0][0] = 1;
for (int a1 = 0;a1 <= a[1];++a1) {
for (int a2 = 0;a2 <= min(a1,a[2]);++a2) {
for (int a3 = 0;a3 <= min(a2,a[3]);++a3) {
for (int a4 = 0;a4 <= min(a3,a[4]);++a4) {
for (int a5 = 0;a5 <= min(a4,a[5]);++a5) {
ll &p = f[a1][a2][a3][a4][a5];//指针储存,传统艺能
if (a1 && a1 > a2) p += f[a1-1][a2][a3][a4][a5];
if (a2 && a2 > a3) p += f[a1][a2-1][a3][a4][a5];
if (a3 && a3 > a4) p += f[a1][a2][a3-1][a4][a5];
if (a4 && a4 > a5) p += f[a1][a2][a3][a4-1][a5];
if (a5) p += f[a1][a2][a3][a4][a5-1];
}
}
}
}
}
printf("%lld\n", f[a[1]][a[2]][a[3]][a[4]][a[5]]);
return 0;
}