题解 P1879 【[USACO06NOV]玉米田Corn Fields】

· · 题解

【思路】

状压DP
状压DP入门题
只需要考虑左右和上下这四个方向所以还是比较轻松的

【什么时候用状压DP呢？】

用状压DP的时候一般数据范围都特别的小
所以看数据范围就可以了

【题目大意】

不和给出序列矛盾，不和上下矛盾，不和左右矛盾
求方案数
第一个矛盾指的是这个方案里面有草的地方和土地贫瘠的地方出现重合
后两个是指上下左右没有草挨着

【核心思路】

先处理出给出的土地贫瘠情况
然后枚举可能出现的每一种情况
判断他是否有左右相邻的草的情况
标记一下
然后就是DP的过程了
枚举的是什么都在下面的循环里面标注出来了

【完整代码】

#include<iostream>
#include<cstdio>
#define int long long 
using namespace std;
const int mo = 1e9;
const int Max = 15;
int a;
int f[Max];//这一行草地的情况 
int ff[Max][5000]; //第i行选j会有多少种方案 
bool s[5000];//左右合不合法 
int read()
{
    int sum = 0,fg = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')fg = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        sum = (sum * 10) + c - '0';
        c = getchar();
    }
    return sum * fg;
}

signed main()
{
    int m = read(),n = read();
    for(register int i = 1;i <= m;++ i)
        for(register int j = 1;j <= n;++ j)
            a = read(),f[i] = (f[i] << 1) + a;
    int MM = (1 << n);
    for(register int i = 0;i < MM;++ i)
        s[i] = ((i & (i << 1)) == 0) && ((i & (i >> 1)) == 0);
    ff[0][0] = 1;//没有是一定成立的qwq 
    for(register int i = 1;i <= m;++ i)//枚举到了第几行 
        for(register int j = 0;j < MM;++ j)//枚举第i行选什么 
            if(s[j] && (j & f[i]) == j)//如果枚举到选择的j是不会出现左右相邻而且不会在这一行不该出现草的地方出现草 
                for(register int k = 0;k < MM;++ k)//枚举i-1行选的什么 
                    if((k & j) == 0)//这两行没有相邻的 
                        ff[i][j] = (ff[i][j] + ff[i - 1][k]) % mo;
    int M = 0;
    for(register int i = 0;i < MM;++ i)
        M += ff[m][i],M %= mo;
    cout << M << endl;
    return 0; 
}