SP15637 GNYR04H - Mr Youngs Picture Permutations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
好题。
考虑从小到大（身高从高到低）安排每个数的位置。
这样，已经被安排的数在每一行肯定占据了最左端连续的一段。否则假设某个人 \(A\) 左面有个空位，这个空位后来被 \(B\) 补齐，由于我们从小到大考虑数，因此 \(A < B\)，然而 \(A\) 却在 \(B\) 的右方，这显然是不合法的。
同理，我们每安排一个数肯定是把它追加到某一行最左侧连续一段的右侧。因此整个过程相当于五行从左到右的填数。
再思考一下从上到下递增这个制约条件。我们发现，如果填数在第一行，那不用管。否则，因为仍然是从小到大填数，所以我们只要保证填这个数 \(B\) 的时候上方有一个数 \(A\) 即可，由于 \(A < B\)，单调性得以满足。而如果上面还没有数，之后上面才被一个数 \(C\) 补齐，就一定不行，因为 \(C > B\)，失去单调性。
同时我们还需要保证每一行的人数不会超限。
考虑 dp，因为个人喜好选择刷表法。
设 \(now = f(a_1, a_2, a_3, a_4, a_5)\) 表示第一行被放置了 \(a_1\) 个数，第二行被放置了 \(a_2\) 个数……第五行被放置了 \(a_5\) 个数时的方案。
我们考虑下一个数是否可以被安排在第 \(i\) 行。有以下两个条件：
- \(a_i + 1 \le n_i\)（不可以超限）；
- \(i = 1 \or a_i + 1 \le a_{i - 1}\)（填这个数时上面必须有数，或者本来就在第一行）；
如果满足这个条件，就可以给 \(f(a_1, \cdots, a_i +1, \cdots, a_5)\) 给出 \(now\) 的贡献。
时间复杂度 \(\mathcal{O}(n^k)\)。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-11-01 01:57:22
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-11-01 02:29:34
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int maxn = 30;
unsigned f[maxn][maxn][maxn][maxn][maxn];
int a[7];
int main() {
int n = 0;
while ((n = read()) && n) {
std :: memset(f, 0, sizeof(f));
std :: memset(a, 0, sizeof(a));
for (int i = 1; i <= n; ++i)
a[i] = read();
f[0][0][0][0][0] = 1;
for (int x1 = 0; x1 <= a[1]; ++x1)
for (int x2 = 0; x2 <= a[2]; ++x2)
for (int x3 = 0; x3 <= a[3]; ++x3)
for (int x4 = 0; x4 <= a[4]; ++x4)
for (int x5 = 0; x5 <= a[5]; ++x5) {
int now = f[x1][x2][x3][x4][x5];
if (x1 < a[1])
f[x1 + 1][x2][x3][x4][x5] += now;
if (x2 < a[2] && x2 < x1)
f[x1][x2 + 1][x3][x4][x5] += now;
if (x3 < a[3] && x3 < x2)
f[x1][x2][x3 + 1][x4][x5] += now;
if (x4 < a[4] && x4 < x3)
f[x1][x2][x3][x4 + 1][x5] += now;
if (x5 < a[5] && x5 < x4)
f[x1][x2][x3][x4][x5 + 1] += now;
}
printf("%u\n", f[a[1]][a[2]][a[3]][a[4]][a[5]]);
}
return 0;
}