传送门
PS:昨天被dalao深深的鄙视了不会状压dp。。。这几天一定要好好练
我们发现，当前行的状态，只与上一行，以及自身内部有关，因此我们的dp数组很好确定，dp[i][state]代表第i行，状态为state的方案数。
ans=sigma(dp[m][state])
因此可以递推来dp，枚举每一行，以及所有合法状态。状态转移：上一行所有合法的状态之和。
关键是怎么确定合法状态
我们可以考虑分两个方面，一个是关于牛和牛之间相邻，一个是关于牛和贫瘠土地的关系。
关于前者，我们可以枚举任何可能的状态，判断该状态 与运算 其左移一位，右移一位是否等于0，如果为0，说明合法。 关于后者，我们枚举所有状态，以及上一步找出来的状态，进行与运算，判断是否变化即可。
#include<bits/stdc++.h> using namespace std; const int mod=100000000; int m,n,field[15][15],hang[15],state[5000],dp[15][5000]; int main() { cin>>m>>n; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>field[i][j]; hang[i]=(hang[i]<<1)+field[i][j]; } } for(int i=0;i<=(1<<n);i++) { state[i]=((i&(i<<1))==0)&&((i&(i>>1))==0);//存储一个状态是否合法 } dp[0][0]=1; for(int i=1;i<=m;i++) { for(int s=0;s<=(1<<n);s++) { if(state[s]&&((s&hang[i])==s))//牛都不相邻 且无冲突(贫瘠) { for(int j=0;j<=(1<<n);j++) { if((j&s)==0) dp[i][s]=(dp[i][s]+dp[i-1][j])%mod; } } } } int ans=0; for(int i=0;i<=(1<<n);i++) ans=(ans+dp[m][i])%mod; cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9400540.html
相关资源：各显卡算力对照表！