思路分析

折腾了我一天的题，希望此题解对其他同学有帮助

（一）：首先分析出性质，根据性质才能想到这道题的dp表示及计算，性质分析出来后，这道题轻松秒掉，首先我们看看y总给的结论

结论：从高到低依次安排每个同学的位置，那么在安排过程中，当前同学一定占据每排最靠左的连续若干个位置，且从后往前每排人数单调递减。否则一定不满足“每排从左到右身高递减，从后到前身高也递减”这个要求。

大家在读完后肯定想证明它是否是对的，但是我想说的是，如果结论这样描述是错误的结论，因为少说了一句话，那就是必须是在每个学生的身高从大到小一个一个放的情况下才是对的，因为少了这句话我搞了一天，加上这句话之后是对的大家可以自己去试几个数或者看看y总的课很容易想出

现在咱们说一个正确的结论：每个学生的身高从大到小一个一个放的情况下，从高到低依次安排每个同学的位置，那么在安排过程中，当前同学一定占据每排最靠左的连续若干个位置，且从后往前每排人数单调递减。否则一定不满足“每排从左到右身高递减，从后到前身高也递减”这个要求。

用蓝书上公式表达就是：

1：a[i] < Ni (a[i]表示第i行的人数， Ni是第i行的最大人数)

2：i = 1 或 a[i-1] > a[i]

学生站在满足上面的式子的一行中，每列学生的身高的单调性也就可以满足

有了这个结论，咱们想一下可以怎么划分阶段，那么就可以通过每一行的人数划分阶了

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

f[a][b][c][d][e]代表从后往前每排人数分别为a, b, c, d, e的所有方案的集合, 其中a >= b >= c >= d >= e；

f[a][b][c][d][e]的值是该集合中元素的数量；

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

当a > b时，最后一个同学可能被安排在第1排，方案数是f[a - 1][b][c][d][e]；

当b > c时，最后一个同学可能被安排在第2排，方案数是f[a][b - 1][c][d][e]；

当c > d时，最后一个同学可能被安排在第3排，方案数是f[a][b][c - 1][d][e]；

当d > e时，最后一个同学可能被安排在第4排，方案数是f[a][b][c][d - 1][e]；

最后一个同学可能被安排在第5排，方案数是f[a][b][c][d][e - 1]；

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 31;
typedef long long ll;

ll dp[N][N][N][N][N];
int k;

int main(){
    while(cin >> k, k){
        int num[6] = {0};//?
        for(int i = 1;i <= k;++i)cin >> num[i];//每一排的人数
        memset(dp, 0, sizeof dp);
        dp[0][0][0][0][0] = 1;
        for(int a = 0;a <= num[1];++a)
            for(int b = 0;b <= min(a, num[2]);++b)
                for(int c = 0;c <= min(b, num[3]);++c)
                    for(int d = 0;d <= min(c, num[4]);++d)
                        for(int e = 0;e <= min(d, num[5]);++e){
                            ll& t = dp[a][b][c][d][e];
                            if(a > b) t += dp[a-1][b][c][d][e];
                            if(b > c) t += dp[a][b-1][c][d][e];
                            if(c > d) t += dp[a][b][c-1][d][e];
                            if(d > e) t += dp[a][b][c][d-1][e];
                            t += dp[a][b][c][d][e-1];
                        }
        cout << dp[num[1]][num[2]][num[3]][num[4]][num[5]] << endl;
    }
}