当前位置:网站首页>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
边栏推荐
- Go zero micro service practical series (IX. ultimate optimization of seckill performance)
- AcWing 346. 走廊泼水节 题解(推公式、最小生成树)
- C language instance_ five
- 制作带照明的DIY焊接排烟器
- 从零开始匹配vim(0)——vimscript 简介
- mongodb查看表是否导入成功
- AcWing 345. Cattle station solution (nature and multiplication of Floyd)
- 2022 Google CTF segfault Labyrinth WP
- 机器学习:随机梯度下降(SGD)与梯度下降(GD)的区别与代码实现。
- AcWing 1142. Busy urban problem solving (minimum spanning tree)
猜你喜欢
云呐|工单管理办法,如何开展工单管理
LeetCode:1175. 质数排列
百度飞将BMN时序动作定位框架 | 数据准备与训练指南 (上)
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
LeetCode:1175. Prime permutation
云呐-工单管理制度及流程,工单管理规范
Make Jar, Not War
对C语言数组的再认识
移植DAC芯片MCP4725驱动到NUC980
[advanced C language] 8 written questions of pointer
随机推荐
黑马笔记---异常处理
LeetCode:1175. 质数排列
【芯片方案设计】脉搏血氧仪
搭建【Redis in CentOS7.x】
长按按钮执行函数
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
云呐-工单管理制度及流程,工单管理规范
Transformation transformation operator
AcWing 346. Solution to the problem of water splashing festival in the corridor (deduction formula, minimum spanning tree)
盒子拉伸拉扯(左右模式)
Transplant DAC chip mcp4725 to nuc980
Neon Optimization: an instruction optimization case of matrix transpose
What does front-end processor mean? What is the main function? What is the difference with fortress machine?
7.6 simulation summary
修改px4飞控的系统时间
从底层结构开始学习FPGA----FIFO IP的定制与测试
Right mouse button customization
设置Wordpress伪静态连接(无宝塔)
736. Lisp 语法解析 : DFS 模拟题
图片打水印 缩放 和一个输入流的转换