【蓝桥每日一题]-动态规划 （保姆级教程 篇12）#照相排列

这次是动态规划最后一期了，感谢大家一直以来的观看，以后就进入新的篇章了

目录

题目：照相排列

思路：  

题目：照相排列

思路：  

    乍一看，好像没什么思路，别急，且听我慢慢分析

    

首先你想模拟这个过程的话，肯定是要动态规划的，因为动态规划是保存过程的。

       

我们要动态规划的话，就会遇到一下问题：

第一个：要开几维的？（题目并没有说具体是几维），同时如何存储每个状态

第二个：如何转移状态？

     

          

首先呢，我们要求的是第一排a人，第二排b人……情况下对应的方案数（也就是排列数）,

我们观察到最大是5排，那就直接设置f[a][b][c][d][e]表示第一排a人，第二排b……情况下对应的方案数，这是最直观的做法。

         

然后就是，如何转移状态呢，那我们不妨从f[0][0][0][0][0]开始模拟一下呗。为了，方便理解，我们暂且假设有至多5个不同的个子：5，4，3，2，1；（从高个子到低个子）

           

     

不难发现：

5 4                 5 4        5

3      是可以由         和3   这两种状态过来的

同理发现：

5 4 1         5 4 1      5 4        

3 2     是由3        和3 2    这两种状态过来的

          

故：发现转移公式f[a,bcde]<=f[a-1,bcde]，f[ab-1, cde]……

         

但是我们不允许出现这种情况：

5 4 

3 2 1

这种情况是不合法的，因为之后来的一定会是更低的人，且会排在1的上面，所以我们至多减少到第一排和第二排人数相等就应该停下了。

        

没错，我们是按照高度从高到低进行安排的，这也就相当于是从f[0][0][0][0][0]开始合法的求解每个种方案解，最终求到我们需要的f[a][b][c][d][e]。

        

至于题上并没有给具体的几排，那我们就默认那一排是0人，也就是不存在那一排即可！！

经过我奋力的解释，最终得到了转移公式：

f[abcde]=f[a-1]+f[b-1]+f[c-1]+f[d-1]+f[e-1]    

         

        
 怕你看不懂代码或者是上面的解释没跟上，单独拿出来再解释一下

for (int b=0; b<=min(a,s[1]); b++)//b不大于a和s[1]

 这一步就是枚举每一排的合法的人数 

 if (a&&a-1>=b) x+=f[a-1][b][c][d][e];//不要引入非法解
 if (b&&b-1>=c) x+=f[a][b-1][c][d][e];
 if (c&&c-1>=d) x+=f[a][b][c-1][d][e];
 if (d&&d-1>=e) x+=f[a][b][c][d-1][e];
 if (e) x += f[a][b][c][d][e-1];//e为0说明没有这一排，不用管了

 这一步是两层含义：

一个是当前排若已经没有人，那就直接不管了

 第二是当前排有人，要减少人数了，但是不能出现非法情况，也就是人数比后面的排多！

#include   
using namespace std;
typedef long long LL;                                                                                          
const int N = 31;
int n;
LL f[N][N][N][N][N];
int main()
{
    while (cin>>n,n)
    {
        int s[5] = {0};
        for (int i=0; i>s[i];
        f[0][0][0][0][0]=1;
        for (int a=0; a<=s[0]; a++)//a是第一排
            for (int b=0; b<=min(a,s[1]); b++)//b不大于a和s[1]
                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 &x = f[a][b][c][d][e];
                            if (a&&a-1>=b) x+=f[a-1][b][c][d][e];//不要引入非法解
                            if (b&&b-1>=c) x+=f[a][b-1][c][d][e];
                            if (c&&c-1>=d) x+=f[a][b][c-1][d][e];
                            if (d&&d-1>=e) x+=f[a][b][c][d-1][e];
                            if (e) x += f[a][b][c][d][e-1];//e为0说明没有这一排，不用管了
                        }
        cout <0]][s[1]][s[2]][s[3]][s[4]]<< endl;
    }
    return 0;
}

各位宝程序员节快乐！累死了，唉