题面
有 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
思路
首先我们先考虑一下，排版的问题，首先每个数从小到大肯定优先排在每一行相对左边的位置，且一行的排列一定是连续的，当你跳过一些点去填下一行，回来再填这一行的话，一定是不符合规则的，那么同理，每一行的长度一定也是递减的。有了这个初步的了解，我们就可以去考虑dp写法了，首先我们拿掉最后一个放置的点，他一定会形成一个映射，就是对于每一行被拿掉的状态，把这些状态相加就是当前的状态数。但是注意这些状态一定要是在我们刚刚的条件和题目的限制下进行转移。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=0;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int ,int> PII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f = -1;
ch=getchar();
}
while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=32;
int s[5];
ll f[maxn][maxn][maxn][maxn][maxn];
int main () {
int n;
while (cin>>n) {
if (n==0) break;
MT (s,0);
MT (f,0);
rev (i,0,n) cin>>s[i];
f[0][0][0][0][0]=1;
rep (a,0,s[0])
rep (b,0,min (a,s[1]))
rep (c,0,min (s[2],b))
rep (d,0,min (s[3],c))
rep (e,0,min (d,s[4])) {
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];
}
printf ("%lld
",f[s[0]][s[1]][s[2]][s[3]][s[4]]);
}
return 0;
}