【题解】洛谷P1879 [USACO06NOV] Corn Fields(状压DP)
2024-09-27 18:13:28
洛谷P1879:https://www.luogu.org/problemnew/show/P1879
思路
把题目翻译成人话
在n*m的棋盘 每个格子不是0就是1
1表示可以种 0表示不能种 相邻的格子不能同时种 求总方案数
把每行看成一个n位的2进制数 预处理出每行的状态后 进行DP即可
PS:在处理每行的初始状态时 将其取反后更好操作
代码
#include<iostream>
#include<cstdio>
using namespace std;
#define mod 100000000
int f[][];
int n,m,ans;
struct State
{
int st[];
int num;
}a[];
void getstate(int i,int t)
{
int num=;//记录此行有几种状态
for(int j=;j<(<<n);j++)//枚举所有状态
{
if((j&t)||(j&(j<<))||(j&(j>>))) continue;//如果冲突就跳过
a[i].st[++num]=j;//记录状态
a[i].num=num;
}
}
void dp()
{
for(int i=;i<=a[].num;i++) f[][i]=;//初始化
for(int i=;i<=m;i++)//枚举行
{
for(int j=;j<=a[i].num;j++)//枚举第i行的状态
{
f[i][j]=;
for(int k=;k<=a[i-].num;k++)//枚举第i-1行的状态
{
if(a[i].st[j]&a[i-].st[k]) continue;//如果冲突就跳过
f[i][j]+=f[i-][k];//累计ans
}
}
}
for(int i=;i<=a[m].num;i++)
ans=(ans+f[m][i])%mod;//累计第m行的所有状态的ans
printf("%d",ans);
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
{
int t=;//处理当前行的状态
for(int j=;j<=n;j++)
{
int x;
cin>>x;//这里对输入进行取反操作
t=(t<<)+-x;//如1010 存成0101 方便后面判断状态
}
getstate(i,t);//获得此行状态
}
dp();
}
最新文章
- Map接口,Map.Entry,hashMap类,TreeMap类,WeakHashMap。
- 开始VS 2012 中LightSwitch系列的第1部分:表中有什么?描述你的数据
- sublime返回上一编辑位置
- 《JavaScript高级程序设计》chapter 1: javascript 简介
- 16.ARC
- Enum(枚举)示例
- HDU 1166 敌兵布阵 线段树的基本应用——动态区间和问题
- eclipse同时开两个tomcat
- 关于sql语句in的使用注意规则( 转)
- oracle_体系结构图_逻辑结构图
- quailty&#39;s Contest #1 A1 道路修建 Small
- be 动词
- LINUX 笔记-iproute2 命令
- RabbitMQ之发布订阅
- 使用docker试用各种软件及docker-ES设置
- C++ 解析Json——jsoncpp(转)
- 强类型Dataset使用事务(改进原有方法)
- Docker:Docker搭建Redis集群(6)
- Python 互斥锁
- 【转】Loadrunner 性能指标定位系统瓶颈
热门文章
- 网站SEO优化
- Csharp:WebClient and WebRequest use http download file
- 谈谈HTML5中的history.pushSate方法,弥补ajax导致浏览器前进后退无效的问题
- Redis学习笔记(二) ---- PHP操作Redis各数据类型
- CentOS 7运维管理笔记(2)----修改命令提示符颜色
- 基础架构之GitLab
- C# 修改GroupBox的边框颜色和字体颜色
- Java基础之异常处理机制
- Linux ->;>; <;user_name>; not in the sudoers file. This incident will be reported.
- C可变参数