栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

玉米田(状压dp)

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

玉米田(状压dp)

###题目内容:
农夫约翰的土地由 M×N 个小方格组成,现在他要在土地里种植玉米。

非常遗憾,部分土地是不育的,无法种植。

而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小,请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 1 行包含两个整数 M 和 N。

第 2…M+1 行:每行包含 N 个整数 0 或 1,用来描述整个土地的状况,1 表示该块土地肥沃,0 表示该块土地不育。

输出格式
输出总种植方法对 108 取模后的值。

数据范围
1≤M,N≤12


思路:首先将玉米田反过来存储,便于用按位与运算判断,然后用b[i]存储第i行的玉米田二进制表示,接着dp得到每一行的状态,如果初始化第0行所有状态为1,那么第一行状态就不需要分开写,否则就要分开写,注意每次都要对10^8取余防止爆内存。

(1)其中j&(j<<1)是判断横向是否有玉米相邻种植
(2)j&b[i]是对当前行玉米地判断是否在不育的地方上种上了玉米
(3)还有就是要与f[i-1][t]按位与,确保上下两行不会冲突
就这三个要点判断

AC代码:
using namespace std;
int a[13][13];
int f[13][16384]; 
int b[13];
int n,m;
int t;
int ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        t=0;
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            a[i][j]=(a[i][j]^1);
            if(a[i][j]==1)
            {
                t+=(1<<(m-j));
            }
         }
         b[i]=t; //存储每行玉米田反二进制表示 
    }
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            for(int j=0;j<(1<
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/738441.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号