2020-2021:teams:farmer_john:2sozx:codeforces_round_668_div._1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_668_div._1 [2020/10/06 10:06] 2sozx [D] |
2020-2021:teams:farmer_john:2sozx:codeforces_round_668_div._1 [2020/10/06 10:17] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| * 题解:溜了溜了 | * 题解:溜了溜了 | ||
| =====E===== | =====E===== | ||
| - | * 题意: | + | * 题意:给定一个 $nm$ 的网格图，问用最少多少个 $1\times x$ 或者 $x\times 1$ 的砖头能够覆盖网格图上所有的 $\#$ ，其中 $x$ 任意，每个砖头长度可以不一致，砖头不能重叠，$n,m\le 200$ |
| - | * 题解: | + | * 题解:显然最劣的方案是全部都用 $1\times 1$ 的矩形，每次合并一个边可以让答案减一。考虑 $L$ 型，显然这种形状必然会用两个砖头，因此考虑每个冲突的 $L$ 型，将 $L$ 型拐弯处的矩形上右两侧连边，因此减去图中的最大独立集即可。 |
| - | =====F===== | + | |
| - | * 题意: | + | |
| - | * 题解: | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_668_div._1.1601949978.txt.gz · 最后更改: 2020/10/06 10:06 由 2sozx
