ZOJ Problem Set – 2563 Long Dominoes 【如压力dp】

ZOJ Problem Set – 2563 Long Dominoes 【如压力dp】

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

称号: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;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116912.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • DTW和DBA_电台文本

    DTW和DBA_电台文本DTW(动态时间调整)动态时间调整算法是大多用于检测两条语音的相似程度,由于每次发言,每个字母发音的长短不同,会导致两条语音不会完全的吻合,动态时间调整算法,会对语音进行拉伸或者压缩,使得它们竟可能

  • vue的双向绑定原理及实现_vue绑定数据

    vue的双向绑定原理及实现_vue绑定数据一、什么是双向绑定我们先从单向绑定切入单向绑定非常简单,就是把Model绑定到View,当我们用JavaScript代码更新Model时,View就会自动更新双向绑定就很容易联想到了,在单向绑定的基础上,用户更新了View,Model的数据也自动被更新了,这种情况就是双向绑定举个栗子当用户填写表单时,View的状态就被更新了,如果此时可以自动更新Model的状态,那就相当于我们把Model和View做了双向绑定关系图如下二、双向绑定的原理是什么我们都知道Vue是数

  • 在计算机中1 KB等于多少字节,字节、kb、MB、GB 等单位怎么换算的?1M等于多少kb,1g等于多少kb?…[通俗易懂]

    在计算机中1 KB等于多少字节,字节、kb、MB、GB 等单位怎么换算的?1M等于多少kb,1g等于多少kb?…[通俗易懂]字节、kb、MB、GB等单位怎么换算的?1M等于多少kb,1g等于多少kb?我们查看文件属性时可以看到很多文件和大小是以kb来显示的,很多朋友都知道电脑中文件大小、容量等采用的是字节、kb、MB、GB等单位,那么你知道它们之间怎么换算的吗,如1M等于多少kb,1g等于多少kb,下面小编就和大家一起来分享下相关知识。1M等于多少kb?1MB=1024KB=1048576字节1G等于多少KB?1G=…

  • Java设计模式(六)之结构型模式:适配器模式

    Java设计模式(六)之结构型模式:适配器模式

  • 中文参数乱码问题——js字符串编码

    中文参数乱码问题——js字符串编码jquery.get中文参数问题——js符串编码摘要:使用jquery.get进行ajax请求获取数据是很常见的操作,一般请求参数都为字母,今天发现在参数中使用中文会出现浏览器兼容性问题,现在记录如下。基本使用语法:$(selector).get(url,data,success(response,status,xhr),dataType)参数 描述url 必需。规定将请求

  • document.cookie与request.cookie

    document.cookie与request.cookie我们知道使用express的cookie中间件,app.use(cookieParser()),这样就可以处理每一个请求的cookie。我们从客户端通过document.cookie获取到当前cookie,作为参数传入后端,在后端设置res.cookie。则之后可在req中获取未过期的cookie。当我们有一个请求时,就可以用res.cookie来将cookie暂时的

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号