ACWing 327. 玉米田
思路:
一颗玉米的上下左右(十字型)放不了–>①上一行第i位有的, 这一行放不了,②同时当前位置不肥沃的也放不了
用到的位运算相关知识(从右往左, 索引为0):
- 将第pos为设置为0:
n=n&(~(1<<pos))
- 将第pos为设置为1:
n=n|(1<<pos)
- 判断第idx位是否为1:
(n&(1<<idx))!=0; // n的第idx位不为1返回真
- 将后n位取反:
int status=pre^((1<<n)-1); // 将pre的后n位取反
代码:
- 递归+记忆化搜索
#include <iostream>
#include <bitset>
#define lli long long int
using namespace std;
const int N=15, MOD=1e8;
int m, n, arr[N][N];
lli dp[N][1<<N];
lli way1(int u, int pre);
lli DFS(int u, int status, int next, int idx);
/* 变量定义:
1. pre: 上一行的状态(0没放, 1放)
2. status:当前行是否能放的状态, 1可以放, 0不能放
3. next: 当前行的放置状态, 1放了, 0没放 ;
*/
// 当前在第u行, 上一行的状态是pre(2), 返回方法数
lli way1(int u, int pre) {
if(dp[u][pre]) return dp[u][pre];
if(u==m+1) return 1; // 不管怎么样都算一种方法
else {
int status=pre^((1<<n)-1);
for(int i=n-1;i>=0;i--) // 进行田地肥沃度判断
if(arr[u][i+1]==0) status=status&(~(1<<i));
dp[u][pre]=DFS(u, status, 0, n-1);
return dp[u][pre];
}
}
// 当前在第u行, 当前行每个位置能否放的状态是status, 当前行的放置状态是next, idx是DFS判断到哪一位了, 返回方法数
lli DFS(int u, int status, int next, int idx) {
if(idx<0) return way1(u+1, next);
else {
lli p1= DFS(u, status, next, idx-1); // 不放
lli p2= ((status&(1<<idx))!=0)? DFS(u, status, (next|(1<<idx)), idx-2): 0;// 放
return (p1+p2)%MOD;
}
}
int main() {
scanf("%d%d", &m, &n);
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d", &arr[i][j]);
cout<<way1(1, 0);
return 0;
}
注意:
用时: 30min
心得:
2024年2月13日16:34:06:
位运算还是得自己憋, 直接看笔记永远记不住