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

经典的线性 \(\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 <bits/stdc++.h>

#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 <int, int> PII;

typedef pair <int, PII> PIII;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 33;

int n, m, k, s[maxn];

LL dp[maxn][maxn][maxn][maxn][maxn];

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	while (1)

	{

		n = gi();

		if (n == 0) break;

		memset(s, 0, sizeof(s));

		for (int i = 1; i <= n; i+=1) s[i] = gi();

		//初始化

		memset(dp, 0, sizeof(dp));

		dp[0][0][0][0][0] = 1;

		//枚举每一排的人数

		for (int a = 0; a <= s[1]; a+=1)

		{

			for (int b = 0; b <= min(a, s[2]); b+=1)

			{

				for (int c = 0; c <= min(b, s[3]); c+=1)

				{

					for (int d = 0; d <= min(c, s[4]); d+=1)

					{

						for (int e = 0; e <= min(d, s[5]); e+=1)

						{

							LL &v = dp[a][b][c][d][e];

							//转移

							if (a && a - 1 >= 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】杨老师的照相排列

最新文章

热门文章