线性dp，271. 杨老师的照相排列

271. 杨老师的照相排列 - AcWing题库

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

第 1 排站在最后边，第 k 排站在最前边。

学生的身高互不相同，把他们从高到底依次标记为 1,2,…,N。

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

问一共有多少种安排合影位置的方案？

下面的一排三角矩阵给出了当 N=6,k=3,N1=3,N2=2,N3=1时的全部 16 种合影方案。注意身高最高的是 1，最低的是 6。

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 表示总排数。

第二行包含 k 个整数，表示从后向前每排的具体人数。

当输入 k=0 的数据时，表示输入终止，且该数据无需处理。

输出格式

每组测试数据输出一个答案，表示不同安排的数量。

每个答案占一行。

数据范围

1≤k≤5,学生总人数不超过 30 人。

输入样例：

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的核心思想是用集合来表示一类方案，然后从集合的维度来考虑状态之间的递推关系。

受上述性质启发，状态表示为：

1.f[a][b][c][d][e]代表从后往前每排人数分别为a, b, c, d, e的所有方案的集合, 其中a >= b >= c     >= d >= e；
2.f[a][b][c][d][e]的值是该集合中元素的数量；

状态计算对应集合的划分，令最后一个同学被安排在哪一排作为划分依据，可以将f[a][b][c][d][e]划分成5个不重不漏的子集：

当a > 0 && a - 1 >= b时，最后一个同学可能被安排在第1排，方案数是f[a - 1][b][c][d][e]；
当b > 0 && b - 1 >= c时，最后一个同学可能被安排在第2排，方案数是f[a][b - 1][c][d][e]；
当c > 0 && c - 1 >= d时，最后一个同学可能被安排在第3排，方案数是f[a][b][c - 1][d][e]；
当d > 0 && d - 1 >= e时，最后一个同学可能被安排在第4排，方案数是f[a][b][c][d - 1][e]；
当e > 0时，最后一个同学可能被安排在第5排，方案数是f[a][b][c][d][e - 1]；
时间复杂度
 

作者：yxc
链接：https://www.acwing.com/solution/content/4954/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

按照上述思路的代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int N = 31;
 
int n;
int s[6];
LL f[N][N][N][N][N];
 
int main() {
	while (scanf("%d", &n) != EOF) {
		if (n == 0)
			break;
		memset(s, 0, sizeof(s));
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= n; i++)
			scanf("%d", &s[i]);
		f[0][0][0][0][0] = 1;
		for (int a = 0; a <= s[1]; a++) {
			for (int b = 0; b <= min(s[2], a); b++) {
				for (int c = 0; c <= min(s[3], b); c++) {
					for (int d = 0; d <= min(c, s[4]); d++) {
						for (int e = 0; e <= min(d, s[5]); e++) {
							if (a && a - 1 >= b)f[a][b][c][d][e] += f[a - 1][b][c][d][e];
							if (b && b - 1 >= c)f[a][b][c][d][e] += f[a][b - 1][c][d][e];
							if (c && c - 1 >= d)f[a][b][c][d][e] += f[a][b][c - 1][d][e];
							if (d && d - 1 >= e)f[a][b][c][d][e] += f[a][b][c][d - 1][e];
							if (e)f[a][b][c][d][e] += f[a][b][c][d][e - 1];
						}
					}
				}
			}
		}
		cout << f[s[1]][s[2]][s[3]][s[4]][s[5]] << endl;
	}
	return 0;
}

 我本人的思路和yxz的差不多，但有一点点不同，看代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int N = 31;
 
int n;
int s[6];
LL f[N][N][N][N][N];
 
int main() {
	while (scanf("%d", &n) != EOF) {
		if (n == 0)
			break;
		memset(s, 0, sizeof(s));
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= n; i++)
			scanf("%d", &s[i]);
		f[0][0][0][0][0] = 1;
		for (int a = 0; a <= s[1]; a++) {
			for (int b = 0; b <= min(s[2], a); b++) {
				for (int c = 0; c <= min(s[3], b); c++) {
					for (int d = 0; d <= min(c, s[4]); d++) {
						for (int e = 0; e <= min(d, s[5]); e++) {
							if (a)f[a][b][c][d][e] += f[a - 1][b][c][d][e];
							if (b)f[a][b][c][d][e] += f[a][b - 1][c][d][e];
							if (c)f[a][b][c][d][e] += f[a][b][c - 1][d][e];
							if (d)f[a][b][c][d][e] += f[a][b][c][d - 1][e];
							if (e)f[a][b][c][d][e] += f[a][b][c][d][e - 1];
						}
					}
				}
			}
		}
		cout << f[s[1]][s[2]][s[3]][s[4]][s[5]] << endl;
	}
	return 0;
}