洛谷P1879：https://www.luogu.org/problemnew/show/P1879
思路
把题目翻译成人话
在n*m的棋盘 每个格子不是0就是1
1表示可以种 0表示不能种 相邻的格子不能同时种 求总方案数
把每行看成一个n位的2进制数 预处理出每行的状态后 进行DP即可
PS：在处理每行的初始状态时 将其取反后更好操作
代码
#include<iostream>
#include<cstdio>
using namespace std;
#define mod 100000000
int f[
15][
1010];
int n,m,ans;
struct State
{
int st[
5000];
int num;
}a[15];
void getstate(
int i,
int t)
{
int num=
0;
//记录此行有几种状态
for(
int j=
0;j<(
1<<n);j++)
//枚举所有状态
{
if((j&t)||(j&(j<<
1))||(j&(j>>
1)))
continue;
//如果冲突就跳过
a[i].st[++num]=j;
//记录状态
a[i].num=
num;
}
}
void dp()
{
for(
int i=
1;i<=a[
1].num;i++) f[
1][i]=
1;
//初始化
for(
int i=
2;i<=m;i++)
//枚举行
{
for(
int j=
1;j<=a[i].num;j++)
//枚举第i行的状态
{
f[i][j]=
0;
for(
int k=
1;k<=a[i-
1].num;k++)
//枚举第i-1行的状态
{
if(a[i].st[j]&a[i-
1].st[k])
continue;
//如果冲突就跳过
f[i][j]+=f[i-
1][k];
//累计ans
}
}
}
for(
int i=
1;i<=a[m].num;i++
)
ans=(ans+f[m][i])%mod;
//累计第m行的所有状态的ans
printf(
"%d",ans);
}
int main()
{
scanf("%d%d",&m,&
n);
for(
int i=
1;i<=m;i++
)
{
int t=
0;
//处理当前行的状态
for(
int j=
1;j<=n;j++
)
{
int x;
cin>>x;
//这里对输入进行取反操作
t=(t<<
1)+
1-x;
//如1010 存成0101 方便后面判断状态
}
getstate(i,t);//获得此行状态
}
dp();
}
转载于:https://www.cnblogs.com/BrokenString/p/9812230.html
相关资源：JAVA上百实例源码以及开源项目
