题意
给定一个最多有 \(5\) 排的一个队伍，每一个位置对应一个同学，给定总人数和第 \(i\) 排 要站 \(n_i\) 个人。
要求每行左边的同学身高要大于右边的，每列从上往下要从大到小。
问：满足要求的一共有多少种方案。
思路
DP
-
首先考虑，在这个题目中，有用的状态有每列最后的人的高度，每行最后的人的高度，每行有多少个人，每列有多少个人这么几个有用的状态。我们显然不可能去考虑这么多状态来进行转移。
-
所以我们直接设一个五维的 DP ，每一维度表示这一行站了几个人了。那么显然， \(dp[i][j][k][l][r]\) 就表示第一行站了 \(i\) 个人 \(\dots\) 的方案数。我们的 DP 目标就是 \(dp[n_1][n_2][n_3][n_4][n_5]\) ,如果行不足 \(5\) ,我们就可以让不足的地方设为 \(0\) 就可以了。
-
而且，我们可以将身高从高到低考虑，这样我们后放的一定比前面放的小，并且我们要满足上面一行放的数目要大于下面一行，否则就有可能不满足列单调递减了。
-
状态转移方程：若 \(a_1 < N_1\) 并且 \(a_1 < a_0\) 时，则有 \(f[a[1]+1][a[2]][a[3]][a[4]][a[5]]+=f[a[1]][a[2]][a[3]][a[4]][a[5]]\) ，之后的转移方程都类似。
代码实现
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 31;
using namespace std;
long long f[N][N][N][N][N];
int n[6],a[6],k;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
signed main()
{
while(scanf("%d",&k) && k)
{
memset(n , 0 , sizeof n);
memset(f , 0 , sizeof f);
for(re int i=1;i<=k;i++) n[i] = read();
f[0][0][0][0][0] = 1;/*啥也不选的方案是1*/
a[0] = 31;/*把a[0]设成超过范围的数，保证a[1]一定小于a[0]*/
for(a[1]=0;a[1]<=n[1];a[1]++)
for(a[2]=0;a[2]<=n[2];a[2]++)
for(a[3]=0;a[3]<=n[3];a[3]++)
for(a[4]=0;a[4]<=n[4];a[4]++)
for(a[5]=0;a[5]<=n[5];a[5]++)
{
if(a[1] < n[1] && a[1] < a[0])
f[a[1]+1][a[2]][a[3]][a[4]][a[5]]+=f[a[1]][a[2]][a[3]][a[4]][a[5]];
if(a[2] < n[2] && a[2] < a[1])
f[a[1]][a[2]+1][a[3]][a[4]][a[5]]+=f[a[1]][a[2]][a[3]][a[4]][a[5]];
if(a[3] < n[3] && a[3] < a[2])
f[a[1]][a[2]][a[3]+1][a[4]][a[5]]+=f[a[1]][a[2]][a[3]][a[4]][a[5]];
if(a[4] < n[4] && a[4] < a[3])
f[a[1]][a[2]][a[3]][a[4]+1][a[5]]+=f[a[1]][a[2]][a[3]][a[4]][a[5]];
if(a[5] < n[5] && a[5] < a[4])
f[a[1]][a[2]][a[3]][a[4]][a[5]+1]+=f[a[1]][a[2]][a[3]][a[4]][a[5]];
}
printf("%lld\n",f[n[1]][n[2]][n[3]][n[4]][n[5]]);
}
return 0;
}