https://www.luogu.com.cn/problem/P4363
晚自修想了十几 min,胡了一个做法。
考虑它这个 \(n,m\) 很小,猜测可能上到指数级别。考虑先分析放的操作,不难发现几个性质。
-
若 \((i,j)\) 能够放置,当且仅当 \((i,j)\) 为空,且 \((1,1),(i,j)\) 这个矩形除了 \((i,j)\) 都已放置。证明显然。
-
每个时刻的放置状态一定呈倒三角阶梯状。即对于每列的行数单调不增。证明考虑下性质 1 即可反证。
那么,这样暴力还是会有 \(10^10\) 状态数。
但是考虑 dp 转移,发现枚举拐点即可。
熄灯了
标签:10,假期,中秋,即可,放置,考虑 From: https://www.cnblogs.com/xugangfan/p/16667478.html