题解 P2132 【小Z的队伍排列】

· · 题解

首先，感谢大佬们对我的启发。

1、题意简述

有5排，从第5排到第1排每排分别为 a,b,c,d,e 个人

a ≥ b ≥ c ≥ d ≥ e ≥ 0

没有的记作0人，问一共有多少种排列方法。

2、题意分析：

本题要用的是动态规划，一个相较于递归更省时间的算法，它可以将之前算过的值储存起来，不像递归一样每推到一个值都要再算一遍。

由于本题最多只有5行，且每行最多30人，那么直接开一个5维的数组 f(30,30,30,30,30) 即可。

不要上来用 "int" ,会有一个点过不了（我就是这样调了一个小时），也不要用 "long long" ,会全暴内存，所以建议用 "unsigned"。 初始值的话就是在每排都是0个人的时候有一种排列方法， $f(0,0,0,0,0) = 1$。 ------------ ## 3、动规方程： 根据题意，每一排的人数都不多于后一排的人数。 当 $a > b > c > d > e > 0$ 时 (保证$a - 1 ≥ b,b - 1 ≥ c,c - 1 ≥ d,d - 1 ≥ e, e - 1 ≥ 0$) $f(a,b,c,d,e) = f(a - 1,b,c,d,e) + f(a,b - 1,c,d,e) + f(a,b,c - 1,d,e) + f(a,b,c,d - 1,e) + f(a,b,c,d,e - 1)

本质上其实是道数学题。

知道方程后，就可以愉快的dp辣。

4、代码：

#include <iostream>
using namespace std;
const int MAXN = 30;
int k,num[6];
unsigned f[MAXN][MAXN][MAXN][MAXN][MAXN];
int main()
{
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> num[i];
    }
    f[0][0][0][0][0] = 1;
    for(int a = 0; a <= num[1]; a++)
        for(int b = 0; b <= num[2]; b++)
            for(int c = 0; c <= num[3]; c++)
                for(int d = 0; d <= num[4]; d++)
                    for(int e = 0; e <= num[5]; e++)
                    {
                        if(a > b) f[a][b][c][d][e] += f[a - 1][b][c][d][e];
                        if(b > c) f[a][b][c][d][e] += f[a][b - 1][c][d][e];
                        if(c > d) f[a][b][c][d][e] += f[a][b][c - 1][d][e];
                        if(d > e) f[a][b][c][d][e] += f[a][b][c][d - 1][e];
                        if(e > 0) f[a][b][c][d][e] += f[a][b][c][d][e - 1];
                    }
    cout << f[num[1]][num[2]][num[3]][num[4]][num[5]];
    return 0;
}

管理员大大求通过！！！本蒟蒻的第一篇正经题解！！！

若有错误，欢迎指出！！！