当前位置:网站首页>ZOJ problem set – 2563 long dominoes [e.g. pressure DP]
ZOJ problem set – 2563 long dominoes [e.g. pressure DP]
2022-07-07 01:37:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
The title of :ZOJ Problem Set – 2563 Long Dominoes
The question : give 1*3 The little rectangle of . Seek cover m*n The maximum number of different methods of the matrix ?
analysis : One of the topics is 1 * 2 Of . It's hot . link : here
This is almost the same , That is, the status of the current line has an impact on the previous line . It also has an impact on the previous line . therefore
Define the State :dp【i】【now】【up】 Said in the first i The row status is now . The status of the previous line is up When the number of programs .
And then the transfer equation :dp【i】【now】【up】 = sum ( dp【i-1】【up】【uup】 ) The premise is legal
The inference of legitimacy is a difficult point to consider . Because it is 1 * 3 Of . It can only be placed horizontally and vertically .
Suppose it is placed horizontally . So above up and uup Of 3 The grid must also be full
Suppose it stands upright , that up and uup The current cell of must be empty , Notice the change after inference up
Suppose you use a simple enumeration dp Words , The fourth level cycle will timeout . So we're going to use up and upp Search deeply to construct the current line , That's how I did it .
AC Code :
#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))) // Vertical placement
dfs(st ,cnt+1 ,now|(1<<cnt) ,up|(1<<cnt) ,upp , num) ;
if(upp&(1<<cnt)) // leave a blank
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++) // The upside
{
for(int st=0; st<(1<<m); st++) // Up and up
{
if(dp[i-1][up][st]) // Pay attention to the inference
dfs(i,0,0,up,st,dp[i-1][up][st]);
}
}
}
printf("%lld\n",dp[n][(1<<m)-1][(1<<m)-1]);
}
return 0;
}
Enumerate timeout codes :
#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))) // Infer the last behavior 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++) // The upside
dp[i][no][kp]=0;
for(int up=0;up<(1<<m);up++) // The upside
{
int temp ;
for(int st=0;st<(1<<m);st++) // Up and up
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;
}
Copyright notice : This article is the original article of the blogger , Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116912.html Link to the original text :https://javaforall.cn
边栏推荐
- Set up [redis in centos7.x]
- AcWing 345. 牛站 题解(floyd的性质、倍增)
- Google released a security update to fix 0 days that have been used in chrome
- 新工作感悟~辞旧迎新~
- 分享一个通用的so动态库的编译方法
- AcWing 346. Solution to the problem of water splashing festival in the corridor (deduction formula, minimum spanning tree)
- AcWing 1148. Secret milk transportation problem solution (minimum spanning tree)
- Transformation transformation operator
- Neon Optimization: performance optimization FAQ QA
- 2022 Google CTF SEGFAULT LABYRINTH wp
猜你喜欢
新工作感悟~辞旧迎新~
AcWing 361. Sightseeing cow problem solution (SPFA seeking positive ring)
云呐-工单管理制度及流程,工单管理规范
一起看看matlab工具箱内部是如何实现BP神经网络的
百度飞将BMN时序动作定位框架 | 数据准备与训练指南 (下)
1123. The nearest common ancestor of the deepest leaf node
MySQL script batch queries all tables containing specified field types in the database
域分析工具BloodHound的使用说明
子网划分、构造超网 典型题
Installation of gazebo & connection with ROS
随机推荐
dvajs的基础介绍及使用
WCF基金会
C语言实例_4
Google发布安全更新,修复Chrome中已被利用的0 day
AcWing 904. 虫洞 题解(spfa求负环)
405 method not allowed appears when the third party jumps to the website
AcWing 1142. Busy urban problem solving (minimum spanning tree)
黑马笔记---异常处理
Table table setting fillet
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
Installation of gazebo & connection with ROS
Js逆向——捅了【马蜂窝】的ob混淆与加速乐
黑马笔记---创建不可变集合与Stream流
免费白嫖的图床对比
从底层结构开始学习FPGA----FIFO IP的定制与测试
移植DAC芯片MCP4725驱动到NUC980
Dark horse notes - create immutable sets and streams
mysqlbackup 还原特定的表
一起看看matlab工具箱内部是如何实现BP神经网络的
Neon Optimization: About Cross access and reverse cross access