玉米田(HG 2018.4.22 T2)

2018-04-22 14:28:05


【题目描述】

FJ 购买了一处肥沃的矩形牧场,分成 M N(1 M 12; 1 N 12) 个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是,有些格子区域的土地是贫瘠的,不能耕种。

精明的 FJ 知道奶牛们进食时不喜欢和别的牛相邻,所以一旦在一个格子中种植玉米,那么他就不会在相邻的格子中种植,即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。

作为一个思想开明的人,FJ 希望考虑所有可行的选择格子种植方案。由于太开明,他 还考虑一个格子都不选择的种植方案!请帮助 FJ 确定种植方案总数。

【输入格式】

第一行包括两个用空格分隔的整数 M 和 N。 接下来的 M 行,每行 N 个数,描述了每行格子是否可以种植的情况(1 表示肥沃的、 适合种植,0 表示贫瘠的、不可种植)。

【输出格式】

输出一个整数,表示 FJ 可选择的方案总数 mod 108 的结果。

【输入输出样例】

cowfood.in

2 3

1 1 1

0 1 0

cowfood.out

9

【 数据规模与约定 】

对于 60% 的数据,1 ≤ M,N ≤ 6

对于 100% 的数据,1 ≤ M,N ≤ 12




同Mondriaan的梦(HG 2018.4.15 试题1 T3)

状压DP一道。用f[i][j]表示第i行状态为j时的方案数。j依然是个二进制数

f[i][j]通过f[i-1][k]转移过来,k是i-1行合法的所有状态(即不和j冲突)

注意:在dfs前先要判断枚举的j是否合法。

#include<map> 
#include<set> 
#include<list> 
#include<cmath> 
#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm> 
using namespace std;
#define MOD 100000000
int n,m;
int a[13][13],f[13][1<<13];
void dfs(int i,int j,int p,int s)
{
    if(p>m) return;
    if(p==m)
    {
        f[i][j]=(f[i][j]+f[i-1][s])%MOD;
        return;
    }
    if((j & (1 << p))==0)
    {
        dfs(i,j,p+1,s);
        dfs(i,j,min(m,p+2),s | (1<<p)); //p+2:保证相邻的两位不会同时种植,种了第p位,p+1必然是不种,可直接跳过
    }
    else dfs(i,j,p+1,s);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j< (1<<m) ;j++)
        {
            int flag=1;
            for(int k=0;k<m;k++)
            {
                if((j & (1<<k)) && a[i][k+1]==0)//如果第k位要种,但是土地贫瘠,不行
                {
                    flag=0;
                    break;
                }
                if((j & (1<<k)) && (j & (1<<(k+1))))//如果有相邻的两位要种,不行
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                dfs(i,j,0,0);
            }
        }
    printf("%d",f[n+1][0]);
    fclose(stdin);
    fclose(stdout);
    return 0;
} 

经过这一道题得出的结论:括号一定不能少加,千万不要为了压行而压行,会死的很惨的