题解：AcWing 271 杨老师的照相排列

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing271. 杨老师的照相排列 - AcWing题库【题目描述】有N NN个学生合影站成左端对齐的k kk排每排分别有N 1 , N 2 , … , N k N_1,N_2,…,N_kN1​,N2​,…,Nk​个人。 (N 1 ≥ N 2 ≥ … ≥ N k N_1≥N_2≥…≥N_kN1​≥N2​≥…≥Nk​)第1 11排站在最后边第k kk排站在最前边。学生的身高互不相同把他们从高到低依次标记为1 , 2 , … , N 1,2,…,N1,2,…,N。在合影时要求每一排从左到右身高递减每一列从后到前身高也递减。问一共有多少种安排合影位置的方案下面的一排三角矩阵给出了当N 6 , k 3 , N 1 3 , N 2 2 , N 3 1 N6,k3,N13,N22,N31N6,k3,N13,N22,N31时的全部16 1616种合影方案。注意身高最高的是1 11最低的是6 66。123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146 45 46 35 36 34 36 34 35 25 26 24 26 24 25 26 25 6 5 6 5 6 4 5 4 6 5 6 4 5 4 3 3【输入】输入包含多组测试数据。每组数据两行第一行包含一个整数k kk表示总排数。第二行包含k kk个整数表示从后向前每排的具体人数。当输入k 0 k0k0的数据时表示输入终止且该数据无需处理。【输出】每组测试数据输出一个答案表示不同安排的数量。每个答案占一行。【输入样例】1 30 5 1 1 1 1 1 3 3 2 1 4 5 3 3 1 5 6 5 4 3 2 2 15 15 0【输出样例】1 1 16 4158 141892608 9694845【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN35;intn,k;// n: 每列人数k: 未使用ints[N],f[N][N][N][N][N];// s: 每列的人数上限f: DP数组记录方案数signedmain(){while(cinn,n)// 循环读入n直到n为0{// if (n0) break; // 被注释掉的结束条件memset(s,0,sizeof(s));// 清空s数组memset(f,0,sizeof(f));// 清空f数组for(inti0;in;i)// 读入每列的人数上限cins[i];f[1][0][0][0][0]1;// 初始状态第一列1人其余列0人for(inta1;as[0];a)// 枚举第一列人数for(intb0;bmin(a,s[1]);b)// 枚举第二列人数且不超过第一列人数for(intc0;cmin(b,s[2]);c)// 枚举第三列人数且不超过第二列人数for(intd0;dmin(c,s[3]);d)// 枚举第四列人数且不超过第三列人数for(inte0;emin(d,s[4]);e)// 枚举第五列人数且不超过第四列人数{// 从a-1,b,c,d,e状态增加一个人到第一列if(a1a-1b)f[a][b][c][d][e]f[a-1][b][c][d][e];// 从a,b-1,c,d,e状态增加一个人到第二列if(b0b-1c)f[a][b][c][d][e]f[a][b-1][c][d][e];// 从a,b,c-1,d,e状态增加一个人到第三列if(c0c-1d)f[a][b][c][d][e]f[a][b][c-1][d][e];// 从a,b,c,d-1,e状态增加一个人到第四列if(d0d-1e)f[a][b][c][d][e]f[a][b][c][d-1][e];// 从a,b,c,d,e-1状态增加一个人到第五列if(e0)f[a][b][c][d][e]f[a][b][c][d][e-1];}coutf[s[0]][s[1]][s[2]][s[3]][s[4]]endl;// 输出最终方案数}return0;}【运行结果】1 30 1 5 1 1 1 1 1 1 3 3 2 1 16 4 5 3 3 1 4158 5 6 5 4 3 2 141892608 2 15 15 9694845 0