自动搬运

查看原文

来自洛谷，原作者为

	lg_zhou 落月摇情满江树

搬运于2025-08-24 22:32:13，当前版本为作者最后更新于2022-05-13 11:31:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实，动规都是想明白后超简单 QaQ

相比楼上的题解没用啥优化，可能实现方法不大一样。

由典型的一道题：炮兵阵地 入手。这道题很显然可以设 $f[i][j][k]$ 代表到 $i$ 行为止，$i$ 行状态是 $j$，$i-1$ 行状态是 $k$，炮兵互不冲突大最大答案。这样的复杂度是枚举阶段的 $n$ 乘状态 $2^m*2^m$ 乘决策，即枚举上面前两行的状态，复杂度为 $O((2^m)^3)$。只是因为有每一行的合法状态很少（相邻两个一中间至少有两个零，大概 $100$ 个），这样才把复杂度减少，从而通过这一题。

然而这一类问题有更普遍的一种解法，就是用更高的进制位（三进制）进行压缩，并存储更多的信息。我们规定放炮兵的位置为 $2$，$2$ 的下面必须放 $1$，$1$ 的下面必须放 $0$。$0$ 的下面才可以任意放。这样我们内存可以省去一维，只用存当前第 $i$ 行的状态

采用正向递推。考虑第 $i+1$ 行填什么状态。需要满足：

1. 第 $i$ 行第 $j$ 位为 $2$ 时，第 $i+1$ 行第 $j$ 位填 $1$
2. 第 $i$ 行第 $j$ 位为 $1$ 时，第 $i+1$ 行第 $j$ 位填 $0$
3. 山地不能填 $2$
4. 一个格子填 $2$ 后，右边两个格子不能填 $2$

因为转移比较复杂，不用写出转移方程，相邻两行进行 $dfs$ 即可。

回到这题，我们将 $2*3$ 和 $3*2$ 的矩阵分别化为

和

与炮兵阵地类似，采用正向递推，需要满足如下条件：

1. 第 $i$ 行第 $j$ 位不为 $0$ 且第 $i+1$ 行第 $j$ 位已损坏，转移失败
2. 第 $i$ 行第 $j$ 位为 $2$ 时，第 $i+1$ 行第 $j$ 位填 $1$
3. 第 $i$ 行第 $j$ 位为 $1$ 时，第 $i+1$ 行第 $j$ 位填 $0$
4. 已损坏的格子填零跳过
5. 可以尝试填上连续三个 $1$ 或者连续两个 $2$

这样这道题就做完了，我做的时候，想过一个问题，就是何时累加答案，若在填连续两个 $2$ 或者连续三个 $1$ 的时候累加，那么最后一行填连续两个 $2$ 显然是不合法的，芯片的下半部分就超出范围了。有两种解决办法，一种是判断一下边界条件，我采用的是另一种，正常做，只不过计算答案的时候直接用 $f[n][0]$ 即可。

内存限制很小，滚动一下就行，改动不大。

放代码，注释很详细：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 155;
const int maxm = 11;
int a[maxn][maxm];
int T,n,m,k;
int f[2][60005];
int pow[11];
void init(){
	pow[0] = 1;
	for (int i = 1; i <= 10; i++) pow[i] = pow[i-1]*3;
}
int suan(int x, int pos){ // 数 x 的三进制第 pos 位是多少 
	return x%pow[pos]/pow[pos-1];
}
bool ifok(int x, int pos, int lst){ // 第 x 行第 pos 位是否能放 
	if (!a[x][pos] && !suan(lst,m-pos+1)) return 1; // 当前位置不能损坏，上一行当前位置必须为零 
	return 0; 
}
void dfs(int x/*这是第几行*/, int lst/*上一行的状态*/, int now/*当前行搜索到的状态*/,  int pos/*从左往右搜到第三进制几位*/, int cnt/*放了几个数了*/){
	if (!pos){ // 更新状态 
		 f[x%2][now] = max(f[x%2][now],f[(x-1)%2][lst]+cnt);
		 return;
	}
	if (suan(lst,pos)){//上一行当前非零 
		if (a[x][m-pos+1]) return;
		if (suan(lst,pos) == 2) dfs(x,lst,now*3+1,pos-1,cnt);
		else dfs(x,lst,now*3, pos-1,cnt); 
	} 
	else{
		dfs(x,lst,now*3,pos-1,cnt);//什么都不放，跳！ 
		if (pos >= 2 && ifok(x,m-pos+1,lst) && ifok(x,m-pos+2,lst)){ //尝试放 3*2 的 （竖的） 
			dfs(x,lst,(now*3+2)*3+2,pos-2,cnt+1); 
		} 
		if (pos >= 3 &&  ifok(x,m-pos+1,lst) && ifok(x,m-pos+2,lst) && ifok(x,m-pos+3,lst)){ //尝试放 2*3 的 （横的） 
			dfs(x,lst,((now*3+1)*3+1)*3+1,pos-3,cnt+1);
		}
	}
}
int main(){
	//freopen("a.in","r",stdin);
	init();
	cin >>T;
	
	while (T--){
		
		cin >> n >> m >> k;
		memset(a,0,sizeof a);
		for (int i = 1; i <= k; i++){
			int x,y;
			cin >> x >> y;
			a[x][y] = 1;
		}
		
		memset(f,-0x3f3f3f3f,sizeof f);
		f[0][0] = 0;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < pow[m]; j++) f[(i+1)%2][j] = -0x3f3f3f3f;
			for (int j = 0; j < pow[m]; j++){
				if (f[i%2][j] < 0) continue;
				dfs(i+1,j,0,m,0);
			}
		}
		cout << f[n%2][0] << endl;
	}
	return 0;
}