自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 21:46:03，当前版本为作者最后更新于2021-09-25 13:18:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不妨按行转移，那么记录上一行伸下来哪些竖笔划。这里的状态数是 $\binom m3 + \binom m2 + \binom m1 + 1$。
即，设状态 $f(i,p_1,p_2,p_3,k)$ 表示第 $i$ 行伸出竖笔划的位置为 $p_1,p_2,p_3$，目前一共有 $k$ 个 L 的方案数。

考虑行间转移，假设这一行有 3 个 L，设它们的最左端分别为 $p_1 < p_2 < p_3$，那么转移有以下几种情况：

1. 凭空出现 3 个 L。
2. 上一行留下 1 个 L 并延续到下一行，在这一行出现 2 个 L。
3. 上一行留下 1 个 L 并截止到这一行，在这一行出现 2 个 L。
4. 上一行留下 2 个 L 并延续到下一行，在这一行出现 1 个 L。
5. 上一行留下 2 个 L 并有 1 个截止，有 1 个延续。在这一行出现 1 个 L。
6. 上一行留下 2 个 L 并截止到这一行，在这一行出现 1 个 L。
7. 上一行留下 3 个 L 并延续到下一行。
8. 上一行留下 3 个 L 并有 1 个截止，有 2 个延续。
9. 上一行留下 3 个 L 并有 2 个截止，有 1 个延续。
10. 上一行留下 3 个 L 并截止到这一行。

然后这一行有 2, 1, 0 个 L 的情况类似讨论即可。

为了计算某个 L 截止到这一行有哪些方案数，需要预处理每个位置右边的第一个障碍物的坐标。

时间复杂度 $O(nm^3)$ 带一个巨大常数（

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 30;
int n,m;
int nxt[N + 5][N + 5];
long long f[N + 5][N + 5][N + 5][N + 5][4];
int main()
{
	scanf("%d%d",&n,&m);
	char ch;
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= m;++j)
		{
			scanf(" %c",&ch);
			if(ch == '#')
				nxt[i][j] = j;
			else
				nxt[i][j] = m + 1;
		}
		for(int j = m - 1;j;--j)
			nxt[i][j] = min(nxt[i][j],nxt[i][j + 1]);
	}
	f[0][0][0][0][0] = 1;
	for(int i = 1;i <= n;++i)
		for(int k = 0;k <= 3;++k)
		{
			f[i][0][0][0][k] += f[i - 1][0][0][0][k];
			for(int p1 = 1;p1 <= m;++p1)
			{
				if(nxt[i][p1] == p1)
					continue;
				if(k < 3)
					f[i][p1][0][0][k + 1] += f[i - 1][0][0][0][k];
				f[i][p1][0][0][k] += f[i - 1][p1][0][0][k];
				f[i][0][0][0][k] += f[i - 1][p1][0][0][k] * (nxt[i][p1] - p1 - 1);
				for(int p2 = p1 + 1;p2 <= m;++p2)
				{
					if(nxt[i][p2] == p2)
						continue;
					if(k < 2)
						f[i][p1][p2][0][k + 2] += f[i - 1][0][0][0][k];
					if(k < 3)
						f[i][p1][p2][0][k + 1] += f[i - 1][p1][0][0][k] + f[i - 1][p2][0][0][k],
						f[i][p2][0][0][k + 1] += f[i - 1][p1][0][0][k] * (min(nxt[i][p1],p2) - p1 - 1),
						f[i][p1][0][0][k + 1] += f[i - 1][p2][0][0][k] * (nxt[i][p2] - p2 - 1);
					f[i][p1][p2][0][k] += f[i - 1][p1][p2][0][k];
					f[i][p2][0][0][k] += f[i - 1][p1][p2][0][k] * (min(nxt[i][p1],p2) - p1 - 1);
					f[i][p1][0][0][k] += f[i - 1][p1][p2][0][k] * (nxt[i][p2] - p2 - 1);
					f[i][0][0][0][k] += f[i - 1][p1][p2][0][k] * (min(nxt[i][p1],p2) - p1 - 1) * (nxt[i][p2] - p2 - 1);
					for(int p3 = p2 + 1;p3 <= m;++p3)
					{
						if(nxt[i][p3] == p3)
							continue;
						if(k < 1)
							f[i][p1][p2][p3][k + 3] += f[i - 1][0][0][0][k];
						if(k < 2)
							f[i][p1][p2][p3][k + 2] += f[i - 1][p1][0][0][k] + f[i - 1][p2][0][0][k] + f[i - 1][p3][0][0][k],
							f[i][p2][p3][0][k + 2] += f[i - 1][p1][0][0][k] * (min(nxt[i][p1],p2) - p1 - 1),
							f[i][p1][p3][0][k + 2] += f[i - 1][p2][0][0][k] * (min(nxt[i][p2],p3) - p2 - 1),
							f[i][p1][p2][0][k + 2] += f[i - 1][p3][0][0][k] * (nxt[i][p3] - p3 - 1);
						if(k < 3)
							f[i][p1][p2][p3][k + 1] += f[i - 1][p1][p2][0][k] + f[i - 1][p2][p3][0][k] + f[i - 1][p1][p3][0][k],
							f[i][p2][p3][0][k + 1] += f[i - 1][p1][p2][0][k] * (min(nxt[i][p1],p2) - p1 - 1) + f[i - 1][p1][p3][0][k] * (min(nxt[i][p1],p2) - p1 - 1),
							f[i][p1][p2][0][k + 1] += f[i - 1][p1][p3][0][k] * (nxt[i][p3] - p3 - 1) + f[i - 1][p2][p3][0][k] * (nxt[i][p3] - p3 - 1),
							f[i][p1][p3][0][k + 1] += f[i - 1][p1][p2][0][k] * (min(nxt[i][p2],p3) - p2 - 1) + f[i - 1][p2][p3][0][k] * (min(nxt[i][p2],p3) - p2 - 1),
							f[i][p1][0][0][k + 1] += f[i - 1][p2][p3][0][k] * (min(nxt[i][p2],p3) - p2 - 1) * (nxt[i][p3] - p3 - 1),
							f[i][p2][0][0][k + 1] += f[i - 1][p1][p3][0][k] * (min(nxt[i][p1],p2) - p1 - 1) * (nxt[i][p3] - p3 - 1),
							f[i][p3][0][0][k + 1] += f[i - 1][p1][p2][0][k] * (min(nxt[i][p1],p2) - p1 - 1) * (min(nxt[i][p2],p3) - p2 - 1);
						f[i][p1][p2][p3][k] += f[i - 1][p1][p2][p3][k];
						f[i][p1][p2][0][k] += f[i - 1][p1][p2][p3][k] * (nxt[i][p3] - p3 - 1);
						f[i][p1][p3][0][k] += f[i - 1][p1][p2][p3][k] * (min(nxt[i][p2],p3) - p2 - 1);
						f[i][p2][p3][0][k] += f[i - 1][p1][p2][p3][k] * (min(nxt[i][p1],p2) - p1 - 1);
						f[i][p1][0][0][k] += f[i - 1][p1][p2][p3][k] * (min(nxt[i][p2],p3) - p2 - 1) * (nxt[i][p3] - p3 - 1);
						f[i][p2][0][0][k] += f[i - 1][p1][p2][p3][k] * (min(nxt[i][p1],p2) - p1 - 1) * (nxt[i][p3] - p3 - 1);
						f[i][p3][0][0][k] += f[i - 1][p1][p2][p3][k] * (min(nxt[i][p1],p2) - p1 - 1) * (min(nxt[i][p2],p3) - p2 - 1);
						f[i][0][0][0][k] += f[i - 1][p1][p2][p3][k] * (min(nxt[i][p1],p2) - p1 - 1) * (min(nxt[i][p2],p3) - p2 - 1) * (nxt[i][p3] - p3 - 1);
					}
				}
			}
		}
	printf("%lld\n",f[n][0][0][0][3]);
}