题目描述

有 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

从左往右数字越来越大，从前往后数字越来越大

DP实质上是对暴搜的优化，此题用dfs也可以实现，但由于种类数很多，dfs的时间复杂度和方案数是成正比的，所以会超时

发现规律：
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

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N=31;//这里的数据大了也会超时……

int n;//排数
LL f[N][N][N][N][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));
        f[0][0][0][0][0]=1;//当每一排都还没有放人的时候，方案数为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 &t=f[a][b][c][d][e];
                            if(a&&a-1>=b)  t+=f[a-1][b][c][d][e];
                            if(b&&b-1>=c)  t+=f[a][b-1][c][d][e];
                            if(c&&c-1>=d)  t+=f[a][b][c-1][d][e];
                            if(d&&d-1>=e)  t+=f[a][b][c][d-1][e];
                            if(e)  t+=f[a][b][c][d][e-1];
                        }
        printf("%lld\n",f[s[0]][s[1]][s[2]][s[3]][s[4]]);
    }
    return 0;
}