拒绝轮廓线 DP，从我做起

· · 题解

不妨按行转移，那么记录上一行伸下来哪些竖笔划。这里的状态数是 \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]);
}