有 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：先考虑一种做法，将同学按高->低编号n-1 并且按此进行方案的选择//好处：保证当前排的同学是最高的且是已排序的同学中最低的 这样一来我们从需要维护集合的全部信息(无序)转移到了只需利用K元组来维护当前每排的数量且只需要考虑插入一个同学(有序) 启发：以后看到类似具有单调的性质，向集合或数组单调性上考虑，化无序为有序，上一张图方便理解记忆：：

代码如下(有参考大神的代码)：

/*************************************************************************
    > File Name: 271.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2021年03月29日 星期一 16时10分16秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 31;
ll f[N][N][N][N][N];
int n,nx[44];
void solve(){
        f[0][0][0][0][0] = 1;
        rep(i,1,30){
            rep(j,0,i){
                rep(p,0,j){
                    rep(k,0,p){
                        rep(t,0,k){
                            if(i)
                            f[i][j][p][k][t] += f[i-1][j][p][k][t];
                            if(j)
                            f[i][j][p][k][t] += f[i][j-1][p][k][t];
                            if(p)
                            f[i][j][p][k][t] += f[i][j][p-1][k][t];
                            if(k)
                            f[i][j][p][k][t] += f[i][j][p][k-1][t];
                            if(t)
                            f[i][j][p][k][t] += f[i][j][p][k][t-1];
                        }
                    }
                }
            }
        }
    while(true){
        read(n);
        if(!n)break;
        memset(nx,0,sizeof nx);
        rep(i,1,n)read(nx[i]);
        write(f[nx[1]][nx[2]][nx[3]][nx[4]][nx[5]]);pc('\n');
    }
}
signed main(){
    solve();
    return 0;
}

作为dp入门级题目，写在最后，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是对该有向无环图的一个拓扑序.节点=状态 边=转移 转移的选取=决策
因此某些时候我们需要将问题变为一张有向无环图进行处理。
动态规划处理问题时通常只需要保留部分信息，观察题目中的变量与不变量，构建状态，应在有些时候抛弃一些无用信息，观察题目中所给的性质。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章