线性DP

作用在线性方向上的递推，$DP$的阶段沿着各个维度线性增长，从一个或多个$“$边界点$”$开始有方向地向整个状态空间转移、扩展，最后每个状态都保留了以自身为目标的子问题的最优解。

这个没什么好说的，看例题叭！

Mr. Youngs Picture Permutations 线性DP

题目描述 杨老师希望给他的班级拍一张合照。 学生们将站成左端对齐的多排，靠后的排站的人数不能少于靠前的排。 此外，杨先生希望每排学生安排高度从左到右减少。此外，学生的身高应该从后面降到前面。 杨先生想知道对于给定的行排列，可能有多少不同的学生安排。

输入格式 每个问题实例的输入将包含两行。第一行给出行数$k$，作为十进制整数。第二行包含从后到前$（n1，n2，...，nk）$的行的长度，作为由单个空格分隔的十进制整数。问题集以行数为$0$结束。行数永远不会超过$5$行，学生总数$N$（行长度之和）最多为$30$。

输出格式 每个问题实例的输出应该是$N$个学生在给定行中的排列数，以便高度沿着每一行从左到右沿着每一列从后到前逐渐减小为十进制整数。（假设所有高度都是不同的。）每个问题实例的结果应该在一个单独的行上。将选择输入数据，以使结果始终适合无符号的$32$位整数。

样例数据

input 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 output 1 1 16 4158 141892608 9694845

不停得超时啊 ~ 超时啊 ~ 超时啊 ~ 超时啊 ~ 然后发现可以把数组放进循环里定义，这样可以保证数组每次最小，memset比较快 题目重要信息：最多只有五行，每行最多30人。 我们设一个五维数组，表示 F[a1][a2][a3][a4][a5]表示第一行站了a1人，第二行站a2人……时的方案数 保证身高从前往后，从左往右依次递减的条件，进行DP即可

#include<bits/stdc++.h> #define ll long long using namespace std; int main() { int a[6], k; scanf("%d", &k); while(k){ for(int i = 1; i <= 5; i++) a[i] = 0; for(int i = 1; i <= k; i++) scanf("%d", &a[i]); ll f[a[1]+1][a[2]+1][a[3]+1][a[4]+1][a[5]+1]; memset(f, 0, sizeof(f)); f[0][0][0][0][0] = 1; for(int a1 = 0; a1 <= a[1]; a1++) for(int a2 = 0; a2 <= a[2]; a2++) for(int a3 = 0; a3 <= a[3]; a3++) for(int a4 = 0; a4 <= a[4]; a4++) for(int a5 = 0; a5 <= a[5]; a5++) { if(a1 < a[1]) f[a1+1][a2][a3][a4][a5] += f[a1][a2][a3][a4][a5]; if(a1 > a2 && a2 < a[2]) f[a1][a2+1][a3][a4][a5] += f[a1][a2][a3][a4][a5]; if(a2 > a3 && a3 < a[3]) f[a1][a2][a3+1][a4][a5] += f[a1][a2][a3][a4][a5]; if(a3 > a4 && a4 < a[4]) f[a1][a2][a3][a4+1][a5] += f[a1][a2][a3][a4][a5]; if(a4 > a5 && a5 < a[5]) f[a1][a2][a3][a4][a5+1] += f[a1][a2][a3][a4][a5]; } printf("%lld\n",f[a[1]][a[2]][a[3]][a[4]][a[5]]); scanf("%d", &k); } return 0; }