AcWing 271. 杨老师的照相排列
本题链接： AcWing 271. 杨老师的照相排列
本博客给出本题截图：
AC代码
代码解释：仔细分析题意后本题有两个性质：
性质1：在每一排中，当前排好位置的人一直在最左边连续的一段
性质2：从上到下每排人数单调递减
f[a][b][c][d][e]代表的是第一排有 a 人，第二排有 b 人，第三排有 c 人，第四排有 d 人，第五排有 e 人的方案数，本题较为简单，其余部分直接看代码即可，在这里不做过多的赘述.
代码：
#include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 31; int n; LL f[N][N][N][N][N]; int main() { while (cin >> n, n) { int s[5] = {0}; 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 <= min(a, s[1]); b ++ ) for (int c = 0; c <= min(b, s[2]); c ++ ) for (int d = 0; d <= min(c, s[3]); d ++ ) for (int e = 0; e <= min(d, s[4]); e ++ ) { LL &x = f[a][b][c][d][e]; if (a && a - 1 >= b) x += f[a - 1][b][c][d][e]; if (b && b - 1 >= c) x += f[a][b - 1][c][d][e]; if (c && c - 1 >= d) x += f[a][b][c - 1][d][e]; if (d && d - 1 >= e) x += f[a][b][c][d - 1][e]; if (e) x += f[a][b][c][d][e - 1]; } cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl; } return 0; }
