P3888 题解

problem & blog。

这怎么评到紫上去的啊？差不多就个上位绿吧 /qd。

首先出题人非常 low。为什么这样说呢？因为 \(nm\le 50,m\le n\) 就是在说 \(m\le 7\)，出题人为了不让你一眼秒掉这一题，就用这种猥琐的方法写数据范围，是不是很傻逼呢。

然后就是状压 DP 板板题了，判断合法状态只需要知道当前行与上一行的选择情况，于是 \(dp_{i,s,t}\) 表示当前是第 \(i\) 行，当前行状态为 \(s\)，上一行状态为 \(t\)，答案（同时记录代价和个数）。

对于连续的三行 \(s,t,p\)，合法转移即：中间行的任意数，要么自己选了，要么相邻的四个位置选了。具体转移

• \(dp_{i,s,t}=\min\limits_{p}\{dp_{i-1,t,p}+(\text{*})\}\)。
• 转移最小花费时 \((\text{*})=\sum\limits_{\text{select j}}^{\text{in line }i} a_{i,j}\)（显然可以预处理）。
• 转移最小个数时 \((\text{*})=\sum\limits_{\text{select j}}^{\text{in line }i} 1\)（即二进制下 \(1\) 的个数）。

初始化 \(+\infty\)，第一行直接算出来，后面 DP，统计答案时枚举最后一行的合法状态，求最优决策即可。

code，时间复杂度 \(O(n2^{3m})\)。由于 \(n,m\) 呈反比例关系，所以 \(n,m\) 显然不可能同时取到最大值，因此很轻松就跑过去啦。