自动搬运

查看原文

来自洛谷，原作者为

	Xy_top constructive thinking

搬运于2025-08-24 22:42:28，当前版本为作者最后更新于2022-12-03 17:09:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到都是顺次转移的动态规划，我来写一个贡献转移。

设 $f[i][j][k]$ 为当前走到第 $i$ 个位置，看了 $j$ 次花，有 $k$ 斗酒的方案数。

题目中说了初始两斗酒，那么 $f[0][0][2]=1$。

重点是怎么前推后，依次循环 $i$，$j$，$k$，

如果 $f[i][j][k]$ 不是 $0$，那么我们在第 $i+1$ 个位置看花或者经过酒店。

看花：走到第 $i+1$ 个位置，看了 $j+1$ 次花，酒的数量变为 $k - 1$。

酒馆：走到第 $i+1$ 个位置，看了 $j$ 次花，酒的数量变为 $k \times 2$。

状态转移方程：

if (f[i][j][k] != 0)//这里也可以简写成 if(f[i][j][k])
{
	f[i + 1][j + 1][k - 1] += f[i][j][k];
	f[i + 1][j][k * 2] += f[i][j][k];
}

注意！$j$ 只需要循环到 $m-1$，不需要循环到 $m$，如果循环到了 $m$：

首先，再看花变成 $m +1$ 已经对答案没有任何的贡献了。

其次，这样还会多算。如果不看花只能是没有酒，一直经过酒店，

但是题目要求最后一次只能经过花，所以不行。

还有一个问题：酒的斗数上线是什么？

显然不会超过 $m$，不然最后的酒就喝不完了，所以也循环到 $m$。

代码：

#include <iostream>
using namespace std;
int n, m;
int f[205][105][105];
int main() {
	cin >> n >> m;
	f[0][0][2] = 1;
	for (int i = 0; i < n + m; i ++)
		for (int j = 0; j < m; j ++)
			for (int k = 0; k <= m; k ++)
				if (f[i][j][k]) {
					if (k > 0) f[i + 1][j + 1][k - 1] = (f[i + 1][j + 1][k - 1] + f[i][j][k]) % 1000000007;
					if (k <= 50) f[i + 1][j][k * 2] = (f[i + 1][j][k * 2] + f[i][j][k]) % 1000000007;
				}
	cout << f[n + m][m][0];
	return 0;
}