动态规划|AcWing 271. 杨老师的照相排列（简单DP）+ 十一届蓝桥杯B组试题E--矩阵算法|c++|动态规划

原题链接：https://www.acwing.com/problem/content/273/
题目描述

有 N 个学生合影，站成左端对齐的 k 排，每排分别有 N1,N2,…,Nk 个人。 (N1≥N2≥…≥Nk)
第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

题解

【动态规划|AcWing 271. 杨老师的照相排列（简单DP）+ 十一届蓝桥杯B组试题E--矩阵】两个性质：
1.在往每一排每一列放置人的时候，每一排已放置的人都是连续的，中间不会有某个地方空缺；
2.每一排已放置的总人数从前往后单调递减

文章图片

从集合的角度思考DP问题：
1.状态表示的方式
所有类型相同的方案都看做一个集合。最多只有五排。
可以用f[a,b,c,d,e] (abcde分别表示第1,2,3,4,5排的人数),表示此状态
1.1考虑状态f[a,b,c,d,e]表示的是哪个集合；
表示所有第一排有a个人，第二排有b个人……的集合
1.2考虑这个集合的属性（这个状态中存的是什么）
属性一般分为三种：这个集合中的元素个数、最大值、最小值
此题即为求元素个数
2.状态的计算（集合的划分）
把整个集合分为若干个子集再相加
一般找到最后的一个不同的点，考虑这个点的取值，来分成若干个子集
注意在划分的时候要不重不漏
但在算最大/小值得时候不重复这个条件可以忽略
此题每一步的最后状态就是最后一个人被安排在了哪一排，则可以分为5个子集，分别为安排在第一排，第二排……
分析每个子集中的元素个数：
若放在第一排使第一排人数为a，方案数应该和第一排人数为a-1时相同，以此类推
但是当某一排人数已满，再放置人就不合理，方案数应为0

#include #include #include using namespace std; typedef long long LL; const int N = 31; LL f[N][N][N][N][N]; int n; int main() { while(scanf("%d", &n) && n) { int s[5] = {0}; //一定要初始化for(int i = 0; i < n; i++) scanf("%d", &s[i]); memset(f, 0, sizeof f); //多组数据一定要重置为0 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 &v = f[a][b][c][d][e]; if(a > 0 && a - 1 >= b) v += f[a - 1][b][c][d][e]; if(b > 0 && b - 1 >= c) v += f[a][b - 1][c][d][e]; if(c > 0 && c - 1 >= d) v += f[a][b][c - 1][d][e]; if(d > 0 && d - 1 >= e) v += f[a][b][c][d - 1][e]; if(e > 0) v += f[a][b][c][d][e - 1]; }cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl; } return 0; }

矩阵题目描述

把 1～2020 放在 2×1010 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以 2020 的余数即可。

#include #include using namespace std; const int N = 1020; typedef long long LL; LL f[N][N]; int main() { f[0][0] = 1; for(int a = 0; a <= 1010; a++) { for(int b = 0; b <= min(a, 1010); b++) { if(a && a - 1 >= b) f[a][b] = (f[a][b] + f[a - 1][b])%2020; if(b) f[a][b] = (f[a][b] + f[a][b - 1])%2020; } } cout << f[1010][1010] << endl; return 0; }