洛谷 P1879 Corn Field G 状压DP解题报告

状压DP的核心是状态压缩，用先前求出的状态推导当前状态，用dp[i][j]表示第i层状态j的方案数

这题是上下左右不能有相邻边，因此前一个状态A 与当前状态B 应该是A&B=0 用B的状态子集A的集合之和就可求出

例如 第三层101 的子集是   000   010 因此dp[3][101]=dp[2][000]+dp[2][010];

还有一些小优化在代码注释里

AC代码如下

#include 
#include 
#include 
using namespace std;
const int N = (1<<12)-1;
vector s[N];
int dp[14][N];
int pas[14];
int n,m;
bool cmp(int a)
{
    for(int i=0;i>i)&1 == 1 && (a>>(i+1))&1 == 1) return false;
    }
    return true;
}//不能有相邻的草地1
int main()
{
    scanf("%d%d",&n,&m);
    int t;
    for(int i=1;i<=n;i++)
        for(int j=0;j 
国庆做一道简单的状压DP找点自信哈哈