当前位置: 首页 > news >正文

1 ACwing 271 Mr

ACwing 271 Mr.Yang's Picture Permutations

题面

有 N 个学生合影,站成左端对齐的 k 排,每排分别有 N1,N2,…,Nk 个人。 (N1≥N2≥…≥Nk)

在合影时要求每一排从左到右身高递增,每一列从后到前身高也递增。

第 i 个人的身高为 i

\(1 \le k \le 5,N \le 30\)

题解

这道题我们可以按照从 1 到 n 的顺序考虑每个人的位置,设每排的人数分别为 \(a_1,a_2,a_3...a_k\)

第 i 个人可以放在第 i 排,当且仅当 \(a_i < N_i\) 并且 \(a_{i - 1} > a_i\)

我们设 \(f[a_1][a_2][a_3][a_4][a_5]\) 表示每排已经放的人数为 \(a_1...\) 的方案数

初始为 \(f(0,0,0,0,0) = 1\) ,目标状态为 \(f(N_1, N_2...)\)\(k\) 不足 5 的我们可以补齐,令 \(N_i\) 为 0 即可

转移(假设放在第 \(1\) 排):\(f(a_1 + 1, a_2...) += f(a_1,a_2...)\)

由均值不等式,最坏情况下有 \((\frac N k ) ^ k\) 个状态,计算每个状态的计算量为 \(O(k)\) 所以总的时间复杂度为 \(O(k(\frac N k)^k)\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;typedef long long ll;const int N = 35;ll f[N][N][N][N][N];int main () {int n;while (cin >> n && n) {int s[5] = {};for (int i = 0; i < n; i++) cin >> s[i];memset (f, 0, sizeof f);f[0][0][0][0][0] = 1;for (int a = 0; a <= s[0]; a ++) {for (int b = 0; b <= s[1]; b ++) {for (int c = 0; c <= s[2]; c ++) {for (int d = 0; d <= s[3]; d ++) {for (int e = 0; e <= s[4]; e ++) {auto now = f[a][b][c][d][e];f[a + 1][b][c][d][e] += now;if (b < a) f[a][b + 1][c][d][e] += now;if (c < b) f[a][b][c + 1][d][e] += now;if (d < c) f[a][b][c][d + 1][e] += now;if (e < d) f[a][b][c][d][e + 1] += now;}}}}}cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=25017

相关文章:

  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744