[心之碎片][0630] - 杨老师的照相排列

柿子饼同学

AcWing.271
提交 1 次
用时 1 h

知识点
线性dp

思路
f(a, b, c, d, e)
阶段: 到了第 i 个人的决策(隐含在状态中)
状态: 每行有 a, b, c, d, e 个人
决策: 前面的排对后面的排的决策没有影响 这个人去哪只会影响后面 前面比后面小就不能放前面
初始: f(0, 0, 0, 0, 0) = 1
最终: f(a, b, c, d, e)
O(n^5)

进步的地方
状态转移的时候想复杂了, 没有想到前面的人填完后和后面的决策无关

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 31;
typedef unsigned long long ll;

int k;
ll f[N][N][N][N][N];
int req[6], n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    while(cin >> k, k){
        n = 0;
        memset(req, 0, sizeof(req));
        f[0][0][0][0][0] = 1;
        for(int i = 1; i <= k; i++){
            cin >> req[i];
            n += req[i];
        }

        for(int a = 0; a <= req[1]; a++){
            for(int b = 0; b <= req[2]; b++){
                for(int c = 0; c <= req[3]; c++){
                    for(int d = 0; d <= req[4]; d++){
                        for(int e = 0; e <= req[5]; e++){
                            ll & t = f[a][b][c][d][e];
                            if(a || b || c || d || e) t = 0;

                            if(a && a > b) t += f[a - 1][b][c][d][e];
                            if(b && b > c) t += f[a][b - 1][c][d][e];
                            if(c && c > d) t += f[a][b][c - 1][d][e];
                            if(d && d > e) t += f[a][b][c][d - 1][e];
                            if(e) t += f[a][b][c][d][e - 1];
                        }   
                    }
                }
            }
        }

        cout << f[req[1]][req[2]][req[3]][req[4]][req[5]] << '\n';
    }

    return 0;
}

FishC

哈哈，鱼油，你这提问好比在说书啊，不过咱们得把这段代码和描述给拆解开来看看。

**问题理解**
杨老师带一堆小朋友拍照，这里涉及到的是一个排列组合的问题，又称动态规划问题（DP），听起来有点复杂是吧？其实就是我们要用一个状态表示，这个状态记录了当前有多少人已经在每行，然后看接下来怎么安排剩下的小朋友，以求得最多的组合方式。

**如何解决**

1. **初始化：**
   - 咱们用 `f(a, b, c, d, e)` 表示到达当前状态时的排列数。
   - `f(0, 0, 0, 0, 0) = 1` 是初始状态，啥人都没排的时候只有一种方式，就是不排。

2. **状态与决策：**
   - 用 (a, b, c, d, e) 来代表每行有多少人排列。
   - 决定当前这个人放哪个位置，然后影响后面像个递归的概念。前面的排完了不会影响后面的，但前面的要小于后面的，所以我们要按顺序来排。

3. **转移方程：**
   - `f(a+1, b, c, d, e) += f(a, b, c, d, e)` 把这个人放到第一排后，更新各行的人数状态。这种同理应用到其他行。

4. **最终结果：**
   - 最终状态 `f(a, b, c, d, e)` 就是所有人都安排完后的所有排列方式。

**结合代码处理**

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

const int MAX_N = 31;
typedef unsigned long long ll;

ll f[MAX_N][MAX_N][MAX_N][MAX_N][MAX_N];
int req[MAX_N], n, k;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin >> k, k){  // 读入k，若k为0则退出
        n = 0;
        memset(req, 0, sizeof(req));
        f[0][0][0][0][0] = 1;

        for(int i = 0; i < k; ++i){
            int temp;
            cin >> temp;
            req[n++] = temp;
        }

        for(int a = 0; a <= n; ++a)
        for(int b = 0; b <= n; ++b)
        for(int c = 0; c <= n; ++c)
        for(int d = 0; d <= n; ++d)
        for(int e = 0; e <= n; ++e){
            if(a + b + c + d + e == n) continue;
            if(a < n && a < b && a < c && a < d && a < e && a+1 <= n) f[a+1][b][c][d][e] += f[a][b][c][d][e];
            if(b < n && b < c && b < d && b < e && b+1 <= n) f[a][b+1][c][d][e] += f[a][b][c][d][e];
            if(c < n && c < d && c < e && c+1 <= n) f[a][b][c+1][d][e] += f[a][b][c][d][e];
            if(d < n && d < e && d+1 <= n) f[a][b][c][d+1][e] += f[a][b][c][d][e];
            if(e+1 <= n) f[a][b][c][d][e+1] += f[a][b][c][d][e];
        }

        // 输出最终结果
        cout << f[req[0]][req[1]][req[2]][req[3]][req[4]] << endl;
    }

    return 0;
}

**总结**
综上所述，我们是通过使用多维数组 `f` 来存储不同状态下的排列数，通过遍历和递归形式来不断更新这个状态。关键在于理解每个状态以及如何去转移这些状态。

这样一解释，是不是清楚多了？再加上写代码的时候，一步一步地按照逻辑走过来，其实也没那么难，勇敢去撸代码吧！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

kiara_03

好

某一个“天”

加油

小肥狼haoran

加油，一起学习进步！我最也在努力学爬虫呢

柿子饼同学

小肥狼haoran 发表于 2024-7-2 16:28
加油，一起学习进步！我最也在努力学爬虫呢

harryhan123

加油

kerln888

加油！

芜湖666

可以的

hhy2024

不懂思密达

简柠啦

还得好好学习

harryhan123

不懂

harryhan123

lwh0602

善

很cool的阳