杨老师拍照问题题解

一、题目分析

题目要求计算满足特定条件的学生排列方式数，关键规则：

1. 每行学生数不超过后一行（从后往前看）；
2. 每行身高从左到右递减；
3. 从后往前看，每行身高也递减。

二、算法思路

1. 动态规划建模：使用五维数组f[i1][i2][i3][i4][i5]表示前5行分别站i1,i2,i3,i4,i5人时的排列方式数；
2. 状态转移：每次选择下一个学生站在哪一行，需满足行内人数不超过前一行（i5<i4<i3<i2<i1）；
3. 边界条件：f[0][0][0][0][0]=1（无人时有一种方式）。

三、代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 31; // 学生总数最大30

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    
    int k;
    while (scanf("%d", &k), k) {
        int a[6] = {0}; // 存储每行人数，索引1-5对应后到前的行
        for (int i = 1; i <= k; ++i) {
            scanf("%d", &a[i]);
        }
        
        // 动态分配五维DP数组（根据输入的行数k，未使用的维度自动为0）
        ll *****f = new ll****[a[1]+1];
        for (int i1 = 0; i1 <= a[1]; ++i1) {
            f[i1] = new ll***[a[2]+1];
            for (int i2 = 0; i2 <= a[2]; ++i2) {
                f[i1][i2] = new ll**[a[3]+1];
                for (int i3 = 0; i3 <= a[3]; ++i3) {
                    f[i1][i2][i3] = new ll*[a[4]+1];
                    for (int i4 = 0; i4 <= a[4]; ++i4) {
                        f[i1][i2][i3][i4] = new ll[a[5]+1];
                        memset(f[i1][i2][i3][i4], 0, sizeof(ll)*(a[5]+1));
                    }
                }
            }
        }
        
        f[0][0][0][0][0] = 1; // 初始状态：无人时1种方式
        
        // 五重循环遍历所有可能的人数组合
        for (int i1 = 0; i1 <= a[1]; ++i1)
            for (int i2 = 0; i2 <= a[2]; ++i2)
                for (int i3 = 0; i3 <= a[3]; ++i3)
                    for (int i4 = 0; i4 <= a[4]; ++i4)
                        for (int i5 = 0; i5 <= a[5]; ++i5) {
                            ll current = f[i1][i2][i3][i4][i5];
                            // 状态转移：尝试将下一个学生放入不同行
                            if (i1 < a[1])
                                f[i1+1][i2][i3][i4][i5] += current;
                            if (i2 < a[2] && i2 < i1)
                                f[i1][i2+1][i3][i4][i5] += current;
                            if (i3 < a[3] && i3 < i2)
                                f[i1][i2][i3+1][i4][i5] += current;
                            if (i4 < a[4] && i4 < i3)
                                f[i1][i2][i3][i4+1][i5] += current;
                            if (i5 < a[5] && i5 < i4)
                                f[i1][i2][i3][i4][i5+1] += current;
                        }
        
        // 输出结果：所有行都站满时的排列数
        printf("%lld\n", f[a[1]][a[2]][a[3]][a[4]][a[5]]);
        
        // 释放动态分配的内存，避免内存泄漏
        for (int i1 = 0; i1 <= a[1]; ++i1) {
            for (int i2 = 0; i2 <= a[2]; ++i2) {
                for (int i3 = 0; i3 <= a[3]; ++i3) {
                    for (int i4 = 0; i4 <= a[4]; ++i4) {
                        delete[] f[i1][i2][i3][i4];
                    }
                    delete[] f[i1][i2][i3];
                }
                delete[] f[i1][i2];
            }
            delete[] f[i1];
        }
        delete[] f;
    }
    
    return 0;
}

四、代码解释

1. 输入处理：

   • 读取行数k和每行人数，存储到数组a[1..k]，未使用的行默认为0；
   • 例如输入3 3 2 1，则a[1]=3, a[2]=2, a[3]=1, a[4]=0, a[5]=0。

2. DP数组初始化：

   • 动态分配五维数组，维度大小由每行人数决定（a[1]~a[5]）；
   • 初始状态f[0][0][0][0][0]=1表示无人时有一种排列方式。

3. 状态转移逻辑：

   • 对于当前人数组合(i1,i2,i3,i4,i5)，尝试将下一个学生放入任意一行：
     • 放入第1行：需满足i1 < a[1]（未站满）；
     • 放入第2行：需满足i2 < a[2]且i2 < i1（人数不超过前一行）；
     • 其余行同理，确保行数从后到前人数非递减。

4. 内存管理：

   • 动态分配的五维数组使用完毕后逐层释放，避免内存泄漏。

五、示例解析

输入：3 3 2 1（3行，人数3-2-1）

1. 状态转移：
   • 从(0,0,0)开始，逐步增加人数，确保i3<i2<i1；
   • 例如i1=3, i2=2, i3=1时，所有行站满，累计所有可能的转移路径数。
2. 输出：16，符合样例要求。

六、复杂度分析

• 时间复杂度：O(n₁×n₂×n₃×n₄×n₅)，其中nᵢ为每行人数，学生总数≤30时复杂度可控；
• 空间复杂度：O(n₁×n₂×n₃×n₄×n₅)，动态分配内存适应不同输入规模。

七、关键技巧

1. 五维DP建模：利用多维数组表示各行列人数组合，直观处理行列约束；
2. 状态转移约束：严格遵循“后行人数≥前行”的条件，确保排列合法性；
3. 动态内存分配：根据输入的每行人数动态分配数组，优化空间使用。