吃水果
$n$ 个小朋友站成一排，等着吃水果。
一共有 $m$ 种水果，每种水果的数量都足够多。
现在，要给每个小朋友都发一个水果，要求：在所有小朋友都拿到水果后，恰好有 $k$ 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同（最左边的小朋友当然不算数，即最左边的小朋友不包含在 $k$ 个小朋友内）。
请你计算，一共有多少种不同的分发水果的方案。
输入格式
一行，三个整数 $n,m,k$。
输出格式
一个整数，表示合理的分发水果的方案总数量对 $998244353$ 取模后的结果。
数据范围
前 $5$ 个测试点满足 $1 \leq n,m \leq 5$。
所有测试点满足 $1 \leq n,m \leq 2000，0 \leq k \leq n−1$。
输入样例1：
1 3 3 0
输出样例1：
3
输入样例2：
3 2 1
输出样例2：
2
解题思路
求方案数，想到用动态规划。一开始定义的状态是$f(i,j,k)$，表示为前$i$个人分配好水果，且第$i$个人分配到水果$j$，且一共有$k$个人的水果与左边的人不一样。状态转移方程就是$$f(i,j,k) = f(i-1,j,k) + \sum\limits_{u=1 ~\&\&~ u \ne j}^{m}{{f(i-1,u,k-1)}}$$
这样做应该是没什么问题的，但很明显这种做法必定会超时，因为状态转移的时间复杂度为$O(n \cdot m^2 \cdot k)$。
事实上可以把第二维的状态给优化掉，定义状态$f(i,j)$表示前$i$个人中恰好有$j$个人拿到的水果与左边的人不一样。根据第$i$个人拿到的水果与左边第$i-1$个人是否相同来进行状态划分，状态转移方程用到了组合计数$$f(i,j) = f(i-1,j) + f(i-1,j-1) \times (m-1)$$
对于第$i$个人拿到的水果与左边第$i-1$个人相同这种情况，意味着前$i-1$个人中恰好有$j$个人拿到的水果与左边的人不一样，对应的方案是$f(i-1,j)$。又因为第$i$个人与第$i-1$个人相同，因此这个集合方案数为$f(i-1,j) \times 1 = f(i-1,j)$。
对于第$i$个人拿到的水果与左边第$i-1$个人不相同这种情况，意味着前$i-1$个人中恰好有$j-1$个人拿到的水果与左边的人不一样，对应的方案是$f(i-1,j-1)$。对于前面任何一种方案固定之后（指前$i-1$个人有$j-1$个不同），因为第$i$个人与第$i-1$个人不相同，因此第$i$个人有$m-1$种选法，因此这个集合方案数为$f(i-1,j-1) \times (m-1)$。
可以发现$f(i-1,j-1) \times (m-1)$是对原先定义的状态$f(i,j,k)$的$~\sum\limits_{u=1 ~\&\&~ u \ne j}^{m}{f(i-1,u,k-1)~}$的优化。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 2010, mod = 998244353;
5
6 int f[N][N];
7
8 int main() {
9 int n, m, k;
10 scanf("%d %d %d", &n, &m, &k);
11
12 f[1][0] = m;
13 for (int i = 2; i <= n; i++) {
14 for (int j = 0; j <= k && j < i; j++) {
15 f[i][j] = f[i - 1][j];
16 if (j) f[i][j] = (f[i][j] + f[i - 1][j - 1] * (m - 1ll)) % mod;
17 }
18 }
19
20 printf("%d", f[n][k]);
21
22 return 0;
23 }
参考资料
AcWing 4496. 吃水果（AcWing杯 - 周赛）：https://www.acwing.com/video/4128/
标签：水果,个人,吃水果,左边,拿到,leq,小朋友 From： https://www.cnblogs.com/onlyblues/p/16630783.html