柿子饼同学 发表于 2024-6-30 14:37:36

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

本帖最后由 柿子饼同学 于 2024-6-30 14:40 编辑

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;
int req, n;

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

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

      for(int a = 0; a <= req; a++){
            for(int b = 0; b <= req; b++){
                for(int c = 0; c <= req; c++){
                  for(int d = 0; d <= req; d++){
                        for(int e = 0; e <= req; e++){
                            ll & t = f;
                            if(a || b || c || d || e) t = 0;

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

      cout << f]]]]] << '\n';
    }

    return 0;
}




FishC 发表于 2024-6-30 14:42:01

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

**问题理解**
杨老师带一堆小朋友拍照,这里涉及到的是一个排列组合的问题,又称动态规划问题(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;
int req, 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 = 1;

      for(int i = 0; i < k; ++i){
            int temp;
            cin >> temp;
            req = 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 += f;
            if(b < n && b < c && b < d && b < e && b+1 <= n) f += f;
            if(c < n && c < d && c < e && c+1 <= n) f += f;
            if(d < n && d < e && d+1 <= n) f += f;
            if(e+1 <= n) f += f;
      }

      // 输出最终结果
      cout << f]]]]] << endl;
    }

    return 0;
}

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

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

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

kiara_03 发表于 2024-7-1 14:41:29

某一个“天” 发表于 2024-7-1 19:57:23

加油

小肥狼haoran 发表于 2024-7-2 16:28:44

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

柿子饼同学 发表于 2024-7-2 18:06:40

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

{:10_275:}

harryhan123 发表于 2024-7-2 18:06:44

加油

kerln888 发表于 2024-7-3 17:13:04

加油!

芜湖666 发表于 2024-7-3 17:15:48

可以的

hhy2024 发表于 2024-7-3 17:23:52

不懂思密达

简柠啦 发表于 2024-7-6 23:12:06

还得好好学习{:10_260:}

harryhan123 发表于 2024-7-12 18:32:41

不懂

harryhan123 发表于 2024-7-12 18:33:15

{:10_266:}

lwh0602 发表于 2024-7-26 15:24:32

很cool的阳 发表于 2024-8-18 10:02:25

{:7_113:}
页: [1]
查看完整版本: [心之碎片][0630] - 杨老师的照相排列