[BZOJ 1725][Usaco2006 Nov]Corn Fields牧场的安排：状压DP_牧场的安排ac-程序员宅基地

点击这里查看原题

用二进制串表示每一行的摆放情况，预处理出各个状态间的转移关系即可。
f[i][j]表示第i行按状态j摆放的方案数。

/*
User:Small
Language:C++
Problem No.:1725
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=(1<<12)+5,mod=1e8;
int f[13][M],n,m,c[M],tot,num[M],d[13],ans;
bool vis[M][M];
void pre(){
    for(int i=0;i<(1<<m);i++){
        if(i&(i>>1)) continue;
        c[++tot]=i;
        for(int j=i;j;j>>=1) num[tot]+=(j&1);
    }
    for(int i=1;i<=tot;i++)
        for(int j=1;j<=tot;j++)
            vis[i][j]=(c[i]&c[j])==0;
}
int main(){
    freopen("data.in","r",stdin);//
    scanf("%d%d",&n,&m);
    pre();
    for(int i=1;i<=n;i++){
        int x;
        for(int j=0;j<m;j++){
            scanf("%d",&x);
            d[i]|=x<<j;
        }
    }
    for(int i=1;i<=tot;i++) if((c[i]&d[1])==c[i]) f[1][i]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=tot;j++){
            if((c[j]&d[i])!=c[j]) continue;
            for(int k=1;k<=tot;k++){
                if(vis[j][k]) f[i][j]=(f[i][j]+f[i-1][k])%mod;
            }
        }
    }
    for(int j=1;j<=tot;j++) ans=(ans+f[n][j])%mod;
    printf("%d\n",ans);
    return 0;
}

本文链接：https://blog.csdn.net/SmallSXJ/article/details/70216200

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

session一些基本的东西_session rolling-程序员宅基地

文章浏览阅读160次。sessionsession是什么session是因为cookie的弊端(存放在客户端，容易被客户修改伪造，数据量大也有纯传输问题) 才被做出来的，用session存储在服务器中，这让他的安全性也相对高一点session是一次浏览器和服务器的交互的会话，session也是一种存储方案服务器建立一个session，会在客户端建立一个唯一的识别(目的是为了只有这个客户端才能获得这个sessionsession的标识也会根据浏览器有关系不同的浏览器的同一用户是不同的标识session 的运作通过_session rolling

Duilib的简单使用（四、换肤）_dulib皮肤-程序员宅基地

文章浏览阅读1.4k次。一、前言在Duilib的简单使用（一、duilib demo）中我们介绍了利用duilib简单的构造一个项目在Duilib的简单使用（二、xml实现界面与业务分离）中我们介绍了XML在duilib中的使用在Duilib的简单使用（三、界面逻辑交互）中我们已经知道如何简单的进行界面的交互这一篇，我们来提一下，Duilib强大的一键换肤功能。二、函数介绍Duilib是一个以贴图为主要表现手段的界面库，实现换肤非常简单，可以通过给控件设置不同的图片来实现换肤，比如给需要换肤的控件调用CControlU_dulib皮肤

SpringMVC常见面试题总结_springmvc面试-程序员宅基地

文章浏览阅读2.1w次，点赞37次，收藏340次。SpringMVC常见面试题总结1. 什么是SpringMVC?SpringMVC是一种基于 Java 的实现MVC设计模型的请求驱动类型的轻量级Web框架，属于Spring框架的一个模块。它通过一套注解，让一个简单的Java类成为处理请求的控制器，而无须实现任何接口。同时它还支持RESTful编程风格的请求。2.什么是MVC模式？MVC的全名是Model View Controller，是模型(model)－视图(view)－控制器(controller)的缩写，是一种软件设计典范。它是_springmvc面试

matplotlib 通过for循环画多张图-程序员宅基地

文章浏览阅读1.2w次，点赞7次，收藏16次。思路利用plt.clf()在每次画完图片后，更新画布。代码#导入两个包import matplotlib.pyplot as pltimport numpy as np #数据准备x = np.arange(27)x = np.reshape(x, (3,9)) #建立for循环语句，绘制x的前三列for i in range(3): plt.plot(x[:,i]) # plt.show() #保存图片的时候不要plt.show() plt.savefig

unity射线检测_unity射线检测对象的tag-程序员宅基地

文章浏览阅读499次。射线检测步骤在代码中声明一个射线，可以是自定义的射线，也可以是鼠标位置或者其他什么的射线，自定义射线（通过定义射线的起始位置和发射方向）：Ray mRay = new Ray(transform.position, transform.forward);或者鼠标射线Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);声明碰撞..._unity射线检测对象的tag

微信小程序设置tabBar选中颜色和图标-程序员宅基地

文章浏览阅读2.9k次。{ "pages":[ "pages/index/index", "pages/logs/logs" ], "window":{ "backgroundTextStyle":"light", "navigationBarBackgroundColor": "#000", "navigationBarTitleText": "首页", "navigationBarTextStyle":"white"//只能black和white }, "t

随便推点

报错The code generator has deoptimised the styling of ...as it exceeds the max of 500KB.-程序员宅基地

文章浏览阅读3.1w次，点赞4次，收藏3次。先贴出报错：字面意思是：babel警告，代码生成器已经将这块js去除了styling, 因为他超过了500KB.解决方案：{ test: /.js$/, exclude: /node_modules/, use: 'babel-loader'},..._the code generator has deoptimised the styling of undefined as it exceeds th

MEMZ木马病毒-程序员宅基地

文章浏览阅读1.3w次，点赞3次，收藏32次。今天做蠕虫弄个memz病毒，把虚拟机搞崩了，重装了一下才解决，详细的了解了一下这种病毒。MEMZ病毒：MEMZ病毒又称彩虹猫病毒，在运行时,该病毒会不断弹窗导致系统无法正常运行，如果尝试结束MEMZ进程或重启系统，桌面会弹出无数个包含“火星文”的消息对话框，随后计算机进入蓝屏状态。重启后，会在屏幕顶部出现一段英文（译文：你的电脑已经被MEMZ病毒损坏，现在一起来欣赏彩虹猫吧），最后出现一个跳跃的“彩虹猫”动画。运行环境：虚拟机！！！！源代码：Github上有源码，不过好像是越南语的注释，不太_memz

python lxml中etree的简单应用3_datas =etree.html(data)-程序员宅基地

文章浏览阅读551次。本次主要介绍，无论使用的xpath表达式中是否包含text()方法，最后都可以获取目标标签下的文本。使用的依然是etree.HTML和etree.tostring方法。1.思路首先将字符串源码转换成_Element对象，然后使用_Element对象的xpath()方法解析xpath表达式。如果通过xpath表达式解析得到的是文本对象，那么先将文本对象（也是字符串）转换成_Element对象，最后通过etree.tostring方法获取_Element对象中的文本内容（可以参考这里）。2.代码实现_datas =etree.html(data)