题解【AcWing271】杨老师的照相排列

标签：inline   bit   tde   stdin   方案   代码   fprintf   air   https   

题面

经典的线性 \(\text{DP}\) 。

设 \(dp_{a,b,c,d,e}\) 表示第 \(1\) 排有 \(a\) 个人，第 \(2\) 排有 \(b\) 个人， 第 \(3\) 排有 \(c\) 个人， 第 \(4\) 排有 \(d\) 个人， 第 \(5\) 排有 \(e\) 个人的方案数。

初始化 \(dp_{0,0,0,0,0}=1\) 。

可以发现一个性质：前排的人数一定比后排的人数多。

转移可以参考代码。

#include 
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi

using namespace std;

typedef long long LL;
typedef pair  PII;
typedef pair  PIII;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c  '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c = b) v += dp[a - 1][b][c][d][e];
                            if (b && b - 1 >= c) v += dp[a][b - 1][c][d][e];
                            if (c && c - 1 >= d) v += dp[a][b][c - 1][d][e];
                            if (d && d - 1 >= e) v += dp[a][b][c][d - 1][e];
                            if (e) v += dp[a][b][c][d][e - 1]; 
                        }
                    }
                }
            }
        }
        //输出结果
        printf("%lld\n", dp[s[1]][s[2]][s[3]][s[4]][s[5]]);
    }
    return 0;
}

题解【AcWing271】杨老师的照相排列

标签：inline   bit   tde   stdin   方案   代码   fprintf   air   https   

原文地址：https://www.cnblogs.com/xsl19/p/12298519.html