查看原题请戳这里
一道五维DP的题目
首先，我们发现，当我们排完部分队形时，已经排好的队形对后续的方案数是有影响的，显然我们这样DP是非常困难的。所以，我们可以选择安装身高顺序插入，每次的决策是第i个人插入的位置。
我们可以发现，如果我们要向第i行的末尾插入一个人，那么第i行的状态必须满足以下两个条件：
$l_i<k_i$
$l_i<l_i-1 \ || \ i = 1 $
第一个条件是保证第i行的人数不会超出上限，第二个条件用来保证列与列直接的单调性。
对于数组的大小，我们发现开$30^5$其实是一个非常大的级别。于是，我们可以这样开：
1
| long long f[31][16][11][9][7];
|
解释一下：
因为第i行的人数一定小于等于第i - 1行的人数，所以第i行最多放$30 / i$个人。
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define qwq printf("qwq\n");
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
long long f[31][16][11][9][7],n,k[100005];
int main()
{
while(1)
{
n = read();
if(!n) break;
memset(k,0,sizeof(k));
memset(f,0,sizeof(f));
f[0][0][0][0][0] = 1;
for(int i = 1; i <= n; i++) k[i] = read();
for(int a = 0; a <= k[1]; a++)
for(int b = 0; b <= k[2]; b++)
for(int c = 0; c <= k[3]; c++)
for(int d = 0; d <= k[4]; d++)
for(int e = 0; e <= k[5]; e++)
{
if(a < k[1])f[a + 1][b][c][d][e] += f[a][b][c][d][e];
if(b < a && b < k[2])f[a][b + 1][c][d][e] += f[a][b][c][d][e];
if(c < b && c < k[3])f[a][b][c + 1][d][e] += f[a][b][c][d][e];
if(d < c && d < k[4])f[a][b][c][d + 1][e] += f[a][b][c][d][e];
if(e < d && e < k[5])f[a][b][c][d][e + 1] += f[a][b][c][d][e];
}
printf("%lld\n",f[k[1]][k[2]][k[3]][k[4]][k[5]]);
}
return 0;
}
|
