算法竞赛进阶指南 玉米田 题解

互联网 2021/4/8 12:13:11

题目大意 农夫约翰的土地由 MN 个小方格组成,现在他要在土地里种植玉米。 非常遗憾,部分土地是不育的,无法种植。 而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。 现在给定土地的大小,请你求出共有多少种种植方法。 土地上什么…

题目大意


 

 

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

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

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

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

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

输出总种植方法对 108 取模后的值。其中1≤M,N≤12

题解


 

 

想了两分钟,和四川省选那道题几乎是一模一样的思路,状态的话由于没有种的个数限制所以少了一维,反而更简单了

要注意的就是对于不能种的田的小技巧,由于与运算的特殊性质,我们一开始就计算好每一行的二进制数

(并且1表示不能种,方便后面与预处理的状态进行与运算)

 

 

程序


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N  = 14,M = 1 << 12,mod = 1e8;

int f[N][M];
vector<int> head[M];
vector<int> state;
int n,m;

int g[N];

inline bool check(int state)
{
    for(int i = 0; i < m - 1; ++ i)
        if((state >> i & 1) && (state >> i + 1 & 1)) return false;
    return true;
}


int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
     for(int j = 0;j < m; ++ j)
      {
          int t;
          cin >> t;
          g[i] += !t * (1 << j);
      }
      
      
    for(int i = 0; i < 1 << m; ++ i)
      if(check(i)) state.push_back(i);
      
    for (int i = 0; i < state.size(); i ++ )
        for (int j = 0; j < state.size(); j ++ )
        {
            int a = state[i], b = state[j];
            if (!(a & b))
                head[i].push_back(j);
        }
      
    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
        for (int j = 0; j < state.size(); j ++ )
            if (!(state[j] & g[i]))
                for (int k : head[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
               
           
    cout << f[n + 1][0] << endl;
    return 0;
           
    
}

 

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[算法竞赛进阶指南 玉米田 题解]http://www.zyiz.net/tech/detail-153787.html

上一篇:企业微信-会话内容存档 实时拉取企业微信聊天记录java版SDK

下一篇:java Stream

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程