VMware matlab向上取整 triggers binding pyqt background Animsition pmp视频教程下载 jq选择第一个子元素 不用u盘装双系统 java手机验证码 ubuntu更改文件夹权限 linux全局搜索文件 mysql时间戳转时间 mysql数据库 python类 python创建txt文件并写入 python中pop函数 java时间 java8特性 怎么安装java环境 jdbc连接mysql java获取当前时间 java命令 java接口调用 java系统学习 linux镜像安装 python视频教程 黑白照片一键变彩色 易语言多线程 mac版matlab ps出血 python列表求和 jsp源代码 小米手环怎么连接手机 刻刀工具 取小数点后两位函数 sql列转行 ps渐变工具在哪里 双通道内存有什么好处
当前位置: 首页 > 学习教程  > 编程语言

P1879 [USACO06NOV]Corn Fields G

2020/8/11 21:01:52 文章标签:

P1879 [USACO06NOV]Corn Fields G

https://www.luogu.com.cn/problem/P1879

首先这道题,一般的区间DP状态不太好设计,很难确定父子关系。

这道题有很鲜明的特征:

1.01矩阵

2.1 ≤ M ≤ 12; 1 ≤ N ≤ 12

所以这就使人很容易想到状压DP

下面详细说说:

f[i][j]表示前[i]行的状态为j时的合法方案数

mp[i]刻画的是土地

possi[i]判断是否合法

步骤:

1.读进来土地,把它二进制转十进制

2.判断草地是否相邻,即是否有连续的1。(i与他的左移一位和右移一位,分别做&运算,如果都都等于0,那么合法)举个例子:

比如说 6→110 (有连续的两个1,是个不合法的)

    1 1 0                 1 1 0

& 0 1 1                 1 0 1

得:0 1 0(×)    1 0 0(×)

3.再枚举每行可能状态,判断是否有种在贫瘠土地上的情况。什么叫种在贫瘠土地上呢?就是原本土地(i,j)这个格子上是个0,你却冒出来个1,就是不行的。这有两种判断合法的方式:(j&mp[i])==j和(j|mp[i])==mp[i]。仍然举个例子:

j       0 1 0                        0 1 0

mp   0 0 1                        0 0 1

&得  0 0 0 (×)     |得: 0 1 1(×)

 AC Code:

#include <bits/stdc++.h>
using namespace std;
const int mo=1e8;
int n,m,maxn,mp[13],f[13][9000],ans;
bool possi[9000];

int main()
{
	int x;
	cin>>m>>n;
	maxn=1<<n;
	f[0][0]=1;
	for(int i=1;i<=m;i++)
	 for(int j=1;j<=n;j++)
	 {
	 	cin>>x;
	 	mp[i]=(mp[i]<<1)+x;//二进制转十进制 
	 }
	 
	for(int i=0;i<maxn;i++)
	 if(!(i&(i<<1))&&!(i&(i>>1)))//判断草地是否相邻 
	  possi[i]=true;
	  
	for(int i=1;i<=m;i++)//枚举每行 
	 for(int j=0;j<maxn;j++)//可能的状态,从00..0.~111..1 
	 {
	 	if(possi[j]&&(j&mp[i])==j)//如果状态合法(没有相邻的1)且没有种在贫瘠的土地上 
	 	 for(int k=0;k<maxn;k++)//找上一行的合法情况 
	 	  if(!(k&j))//与该行状态取&不为真(0)
		   //说明上一行与这一行不存在任意一块草地有公共边
	 	   f[i][j]=(f[i][j]+f[i-1][k])%mo;//记录 
	 }
	 for(int i=0;i<maxn;i++)
	  ans=(ans+f[m][i])%mo;
	  
	  cout<<ans<<endl;
	  return 0;
}   
  

 


本文链接: http://www.dtmao.cc/news_show_100460.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?