P1879 [USACO06NOV]玉米田Corn Fields 原题地址
可以用一个n位二进制数表示一行的一种种植状态, 如010表示n = 3时在中间位置种植, 旁边两个位置不种植的状态.
对于长为n的一行, 若不考虑有些位置不可以种植以及不能够相邻种植的约束, 那么总共有1 << n(2的n次方)种植状态.
所以代码中首先初始化, 遍历长为n的一行的所有种植状态, 即遍历在[0, 1 << n)范围内的整数. 对于[0, 1 << n)中的整数i, 若 (i & (i << 1))不等于0, 则i的二进制表达式中存在连续的1, 也就是i表示的状态存在相邻种植, 是不可以使用这种状态的.而除这种状态之外的所有状态, 则存储到status数组中.
对于每一行, 输入了可以种植与不可种植的位置, 用一个整数表示一行的情况, 该整数的每一个二进制位对应一个位置是否可以种植, 0表示可以, 1表示不可以(注意根输入的表示相反), 使用数组row, row[i]为表达第i行情况的整数. 那么对于status中的每个状态, 若status[j] & row[i] == 0, 就表示第j种状态适用于第i行.
然后开始DP. dp[i][j]表示第i行选择status中的第j种状态的方案数量. 第0行进行特殊处理, 其余每行i, 遍历status中的状态, 若row[i] & status[j] == 0, 则第j种状态可以在第i行中实现, 此时对于第i - 1行(上一行), 再次遍历status中的状态, 若row[i - 1] & status[k] == 0, 即第k种状态适用于第i - 1行, 此时若status[j] & status[k] == 0, 意思就是第i行选择的第j种状态和第i - 1行选择的第k种状态是兼容的, 不会造成上下行相邻种植. 那么dp[i][j]就要加上dp[i - 1][k].
更多见代码注释.
#include "stdio.h"
#include "stdlib.h"
#define maxm 12
#define maxnum 0x1000 /* 1 << 12 */
#define mod 100000000
int status[maxnum], top;
int row[maxm];
int dp[maxm][maxnum];
//初始化
void init(int n) {
int p = 1 << n; //最多可能的种植状态数量
top = 0;
for (int i = 0; i < p; i++) { //遍历每种状态
//若没有相邻种植, 则记录i
if (!(i & (i << 1))) status[top++] = i;
}
}
int main() {
int m, n;
scanf("%d %d", &m, &n);
init(n);
int flag;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &flag); //输入, 1表示可以种植, 0表示不可以
//row[i]的二进制位, 1表示不可种植, 0表示可以
//初始时row[i]=0, 所有二进制位为0
if (!flag) row[i] += (1 << (n - j - 1)); //输入为0, 则row[i]相应的二进制位更新为1
}
}
//对于第0行特殊处理
for (int i = 0; i < top; i++) {
if (!(status[i] & row[0])) dp[0][i] = 1; //若status[i]适用于第0行
}
for (int i = 1; i < m; i++) { //遍历1至m-1行
for (int j = 0; j < top; j++) {
if (status[j] & row[i]) continue; //status[j]不适用于第i行, 则continue
//找到一个适用于第i行的status[j]
for (int k = 0; k < top; k++) {
if (status[k] & row[i - 1]) continue; //status[k]不适用于第i - 1行, 则continue
//找到一个适用于第i - 1行的status[k]
if (status[j] & status[k]) continue; //若status[j]与status[k]不兼容, 则continue
//到这里第i行选择的第j种状态和第i - 1行选择的第k种状态是兼容的
dp[i][j] += dp[i - 1][k];
dp[i][j] %= mod;
}
}
}
int res = 0;
for (int i = 0; i < top; i++) {
res += dp[m - 1][i];
res %= mod;
}
printf("%d", res);
return 0;
}