ZOJ problem set – 2563 long dominoes [e.g. pressure DP]

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;
}

Copy

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;
}

Copy

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