[CF111C Petya] and Spiders

题目

洛谷

思路

首先， $min(n,m)<=6$ 是很容易判断出来的。

于是我想着：这么小的数据范围，能够直接分类讨论吗？但由于是状压dp板块的题，也没有从这方面细想，题解中似乎有分类讨论的做法。

想状压dp的做法。由于之前状压dp做得太少，实在是没什么想法。看了题解梳理一下。

由于蜘蛛可以往上下左右四个方向走，以及原地待着，我们将题目转化为：在棋盘上选一些点，点可以覆盖上下左右即自身，求最少多少点可以将棋盘完全覆盖。

定义 $dp[i][k1][k2]$ 为第 $i$ 行状态为 $k1$， $i-1$ 行为 $k2$ 的最小点数。因为只有上中下三行对第 $i$ 行会有影响，所以这样考虑状态不会有缺漏。

状态转移为 $dp[i][k1][k2]=min(dp[i-1][k2][k3]+count(k1))$

Code

LL n, m, dp[MAXM][MAXN][MAXN];
// dp[i][k1][k2] : 
// 第 i 行状态为 k1 ,第 i-1 行状态为 k2 的最小点数
inline LL Count(LL Zt)
{LL Res = 0;
// for (Int i = 0; i < m; ++ i)
// Res += (Zt & (1 << i));for (Int i = 0; i < m; ++ i)if (Zt & (1 << i))Res ++;return Res;
}
int main()
{read( n ); read( m );if (n < m)Swap(n, m);LL Ans = INF, Top = (1 << m) - 1;memset(dp, 0x3f, sizeof dp);for (Int i = 0; i <= Top; ++ i){dp[1][i][0] = Count( i );// printf("%d %lld\n", i, dp[1][i][0]);if (n == 1){bool Flag = 0;for (Int j = 0; j < m; ++ j)if (! (i & Nw( j ) || (j > 0 && i & Nw(j - 1)) || (j < m - 1 && i & Nw(j + 1)))){Flag = 1;continue;}if (! Flag)Ans = Min(Ans, dp[1][i][0]);}}for (Int i = 2; i <= n; ++ i) // 行数 {for (Int k3 = 0; k3 <= Top; ++ k3) // 上上行 for (Int k2 = 0; k2 <= Top; ++ k2) // 上一行，将上一行当做中间 for (Int k1 = 0; k1 <= Top; ++ k1) // 当前行 {bool Flag = 0;for (Int j = 0; j < m; ++ j)if (! (k1 & Nw( j ) || k2 & Nw( j ) || k3 & Nw( j ) || (j > 0 && k2 & Nw(j - 1)) || (j < m - 1 && k2 & Nw(j + 1)))){Flag = 1;break;}if ( Flag )continue;dp[i][k1][k2] = Min(dp[i][k1][k2], dp[i - 1][k2][k3] + Count( k1 ));if (i == n){Flag = 0;for (Int j = 0; j < m; ++ j)if (! (k1 & Nw( j ) || k2 & Nw( j ) || (j > 0 && k1 & Nw(j - 1)) || (j < m - 1 && k1 & Nw(j + 1)))){Flag = 1;break;}if ( Flag )continue;Ans = Min(Ans, dp[i][k1][k2]);}}}printf("%lld", n * m - Ans);return 0;
}