题目链接 https://loj.ac/problem/2731 题解 首先一个很自然的思路是，设\(dp[i][j]\)表示选了前\(i\)列，第\(2\)行第\(i\)列的格子是第\(j\)个被填上的。 还要加个第三维\(0/1\)，表示第\(2\)行第\(i\)列不是/是这一列最后一个被填上的（这决定了它是被上下填上还是被左右填上）。 转移: 若第\(2\)行第\(i\)列是棋子，则所有的

题目链接 https://loj.ac/problem/2733 题解 神仙题…… 首先可以观察到一个结论: 目标块的两块小三明治一定分别是最后和倒数第二个被吃的。 由此我们可以考虑这两块谁先被吃。这样的好处就是，起初我们一个块被吃的依赖条件是某两个块中有一个被吃就行，现在两个块中的某一个已经钦定了比它更晚，另一个就一定要比它早，这样依赖关系就形成了一张图。 那么有一个\(O(n^4)\)的做法