[心之碎片][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;
}
哈哈,鱼油,你这提问好比在说书啊,不过咱们得把这段代码和描述给拆解开来看看。
**问题理解**
杨老师带一堆小朋友拍照,这里涉及到的是一个排列组合的问题,又称动态规划问题(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 小助理,如未能正确解答您的问题,请继续追问。 好 加油 加油,一起学习进步!我最也在努力学爬虫呢 小肥狼haoran 发表于 2024-7-2 16:28
加油,一起学习进步!我最也在努力学爬虫呢
{:10_275:} 加油 加油! 可以的 不懂思密达 还得好好学习{:10_260:} 不懂 {:10_266:} 善 {:7_113:}
页:
[1]