当前位置:网站首页>ZOJ Problem Set – 2563 Long Dominoes 【如压力dp】
ZOJ Problem Set – 2563 Long Dominoes 【如压力dp】
2022-07-06 17:57:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
称号:ZOJ Problem Set – 2563 Long Dominoes
题意:给出1*3的小矩形。求覆盖m*n的矩阵的最多的不同的方法数?
分析:有一道题目是1 * 2的。比較火。链接:这里
这个差点儿相同,就是当前行的状态对上一行有影响。对上上一行也有影响。所以
定义状态:dp【i】【now】【up】表示在第 i 行状态为now 。上一行状态为 up 时的方案数。
然后转移方程:dp【i】【now】【up】 = sum ( dp【i-1】【up】【uup】 ) 前提是合法
合法性的推断是比較难考虑的一点。由于是1 * 3的。仅仅能横着放和竖着放。
假设横着放。那么上面up 和 uup 的 3 格也必须是满的才行
假设竖着放,那么up 和 uup的当前格必须是空的,注意推断后变化up
假设用简单的枚举dp的话,四层循环会超时。所以我们要用up 和 upp 来深搜构造当前行,这样才干过。
AC代码:
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INT long long int
const long long N = 9 ;
const int inf = 0x3f3f3f3f;
INT dp[31][1<<N][1<<N];
int m,n;
bool Judge(int s,int up,int upp)
{
for(int i=s;i<s+3;i++)
if(!(up&(1<<i)) || !(upp&(1<<i)))
return false;
return true;
}
void dfs(int st,int cnt,int now,int up,int upp,INT num)
{
if(cnt==m)
{
dp[st][now][up]+=num;
return ;
}
if(cnt+3<=m && Judge(cnt,up,upp)) //heng
dfs(st,cnt+3,now|(1<<cnt)|(1<<(cnt+1))|(1<<(cnt+2)),up,upp,num);
if(!(up&(1<<cnt))&&!(upp&(1<<cnt))) // 竖放
dfs(st ,cnt+1 ,now|(1<<cnt) ,up|(1<<cnt) ,upp , num) ;
if(upp&(1<<cnt)) //留空
dfs(st ,cnt+1 ,now ,up ,upp ,num) ;
}
int main()
{
while(~scanf("%d%d",&m,&n)&& m+n)
{
memset(dp,0,sizeof(dp));
dfs(1,0,0,(1<<m)-1,(1<<m)-1,1);
for(int i=2; i<=n; i++)
{
for(int up=0; up<(1<<m); up++) //上行
{
for(int st=0; st<(1<<m); st++) //上上行
{
if(dp[i-1][up][st]) //注意一定推断
dfs(i,0,0,up,st,dp[i-1][up][st]);
}
}
}
printf("%lld\n",dp[n][(1<<m)-1][(1<<m)-1]);
}
return 0;
}
枚举超时代码:
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INT long long int
const long long N = 9 ;
const int inf = 0x3f3f3f3f;
INT dp[31][1<<N][1<<N];
int m,n;
bool isit(int st)
{
int tmp=0;
for(int i=0;i<m;i++)
{
if(st&(1<<i))
tmp++;
else
{
if(tmp%3)
return false;
}
}
if(tmp%3)
return false;
return true;
}
INT solve(int now,int up,int uup)
{
for(int i=0;i<m;i++)
{
if(!(uup&(1<<i))) //推断上上一行为0
{
if(up&(1<<i))
return -1 ;
else
{
if(!(now&(1<<i)))
return -1 ;
else
up |= (1<<i) ;
}
}
else
{
if(up&(1<<i) && now&(1<<i)) // 1 1 1
{
if(i==m-2 || i==m-1)
return -1 ;
else if(!(now&(1<<(i+1))) || !(now&(1<<(i+2))) || !(up&(1<<(i+1))) || !(up&(1<<(i+2))) || !(uup&(1<<(i+2))) || !(uup&(1<<(i+1))))
return -1 ;
i+=2;
}
}
}
return up ;
}
int main()
{
while(~scanf("%d%d",&m,&n)&& m+n)
{
for(int st=0;st<(1<<m);st++)
{
if(!isit(st))
continue;
for(int up=0;up<(1<<m);up++)
{
if(isit(up)){
dp[2][st][up]=1;
}
}
}
for(int i=3;i<=n;i++)
{
for(int no = 0;no < (1<<m); no++)
{
for(int kp=0;kp<(1<<m);kp++) //上行
dp[i][no][kp]=0;
for(int up=0;up<(1<<m);up++) //上行
{
int temp ;
for(int st=0;st<(1<<m);st++) //上上行
if((temp = solve(no,up,st)) != -1)
dp[i][no][temp]+=dp[i-1][up][st];
//printf("%d\n",dp[i][up][up]);
}
}
}
printf("%lld\n",dp[n][(1<<m)-1][(1<<m)-1]);
}
return 0;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116912.html原文链接:https://javaforall.cn
边栏推荐
- 字节P7专业级讲解:接口测试常用工具及测试方法,福利文
- Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
- curl 命令
- 【芯片方案设计】脉搏血氧仪
- 剑指 Offer II 035. 最小时间差-快速排序加数据转换
- Send template message via wechat official account
- NEON优化:关于交叉存取与反向交叉存取
- Let's see through the network i/o model from beginning to end
- C language instance_ five
- 云呐-工单管理制度及流程,工单管理规范
猜你喜欢
修改px4飞控的系统时间
云呐|工单管理办法,如何开展工单管理
How to manage distributed teams?
Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
boot - prometheus-push gateway 使用
LLDP兼容CDP功能配置
【信号与系统】
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
C language - array
随机推荐
Asset security issues or constraints on the development of the encryption industry, risk control + compliance has become the key to breaking the platform
各种语言,软件,系统的国内镜像,收藏这一个仓库就够了: Thanks-Mirror
一起看看matlab工具箱内部是如何实现BP神经网络的
taro3.*中使用 dva 入门级别的哦
Gnet: notes on the use of a lightweight and high-performance go network framework
go-zero微服务实战系列(九、极致优化秒杀性能)
What does front-end processor mean? What is the main function? What is the difference with fortress machine?
Dark horse notes - exception handling
LeetCode:1175. 质数排列
Meet in the middle
C language instance_ three
Neon Optimization: an optimization case of log10 function
如何管理分布式团队?
Taro 小程序开启wxml代码压缩
增加 pdf 标题浮窗
Supersocket 1.6 creates a simple socket server with message length in the header
736. Lisp 语法解析 : DFS 模拟题
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
今日问题-2022/7/4 lambda体中修改String引用类型变量
JTAG debugging experience of arm bare board debugging