杨老师的照相排列
2022/2/14 23:44:25
本文主要是介绍杨老师的照相排列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目分析
dp的难点在于状态的确定和转移方程的推导.
在本题中,我们可以从头枚举,去观察归纳,找到本题的最优子结构.
假设有\(k=1,a=[3,2,1]\).对于第一个数字1,它的数字一定是固定的——只能在最左上角;对于第二个数字,它可以位于1的右边,也可以在1的下边……
通过列举摆放的情况后,我们可以发现:
-
第\(i\)行的摆放数字的数量不超过\(a_i\)
-
除了第一行之外,其他行摆放的数量都不超过上一行
为了保证题目中的要求,每个元素安放位置的枚举顺序也是按照从小到大开始的,那么我们可以让枚举过的元素组成一个集合,可以发现,元素放置的位置,即放置好的元素构成的形状,影响当前这个集合对应的方案数量
这样可以将一个子结构定义成f[a1][a2][a3][a4][a5]
,\(a_k\)代表第\(k\)行摆放的元素的数量,对于摆放行数不够的情况,默认摆放成0
这样一来,我们就可以得到转移方程:在合法的情况下,f[]...[k + 1]... += f[]...[k]...
边界条件为f[0][0][0][0][0]=1
代码
#include <iostream> #include <cstring> using namespace std; typedef long long LL; constexpr int N = 33; LL f[N][N][N][N][N]; int n; int s[N]; int main() { while (scanf("%d", &n), n) { memset(f, 0, sizeof f); memset(s, 0, sizeof s); for (int i = 1; i <= n; i++) scanf("%d", &s[i]); f[0][0][0][0][0] = 1; for (int a1 = 0; a1 <= s[1]; a1++) for (int a2 = 0; a2 <= min(a1, s[2]); a2++) for (int a3 = 0; a3 <= min(a2, s[3]); a3++) for (int a4 = 0; a4 <= min(a3, s[4]); a4++) for (int a5 = 0;a5 <= min(a4, s[5]); a5++) { LL &x = f[a1][a2][a3][a4][a5]; if (a1 < s[1]) f[a1+1][a2][a3][a4][a5] += f[a1][a2][a3][a4][a5]; if (a2 < s[2]) f[a1][a2+1][a3][a4][a5] += f[a1][a2][a3][a4][a5]; if (a3 < s[3]) f[a1][a2][a3+1][a4][a5] += f[a1][a2][a3][a4][a5]; if (a4 < s[4]) f[a1][a2][a3][a4+1][a5] += f[a1][a2][a3][a4][a5]; if (a5 < s[5]) f[a1][a2][a3][a4][a5+1] += f[a1][a2][a3][a4][a5]; } printf("%lld\n", f[s[1]][s[2]][s[3]][s[4]][s[5]]); } return 0; }
这篇关于杨老师的照相排列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行