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)


相关推荐

  • 不同组织的窗宽窗位

    不同组织的窗宽窗位头颅,脑组织:窗宽设定为80Hu~100Hu,窗位为30Hu~40Hu,垂体及蝶鞍区病:变窗宽宜设在200Hu~250Hu,窗位45Hu~50Hu,脑出血患者可改变:窗宽位80Hu~140Hu,窗位30Hu~50Hu,脑梗死患者:常用窄窗60Hu,能提高病灶的检出率,清楚显示梗死及软化灶,颌面部眼眶:窗宽定为150Hu~250Hu,窗位30Hu~40Hu,…

  • Laravel中用GuzzleHttp

    Laravel中用GuzzleHttp

    2021年10月24日
  • AC自动机和Fail树

    Fail树与阿狸的打字机萌新第一次试着写博客…全是口胡(/□\*),可能以后也不会有时间再写了相关数据结构:AC自动机,树状数组(线段树)Fail指针的基本性质:某只结点的Fail指针,指向它所代表的字符串的最长的后缀的结点。性质:每只结点沿着其Fail指针一直走,最终会走到根节点。这样,将每只结点和其Fail指针指向的结点连边,就形成了一个树,其根与原Trie树相同,称为Fail树。…

  • getmethod方法什么意思_getstring方法

    getmethod方法什么意思_getstring方法getMethod方法要注意的地方:类对象.getMethod(mName,HttpServletRequest.class,HttpServletResponse.class);第一个参数是mName“方法名称”第二个参数是“方法参数的类对象”//这个就是为什么他是.class的原因,为什么参数是类对象?因为这个是Java规定的举个例子  这是一个抽取出的通用的servlet(页面请求经过的第…

  • canbus速率_erie canal

    canbus速率_erie canalDatabus和canal都能够提供实时从数据库获取变更,并提供给下游的实时消费流的功能。本文针对两个系统实现和应用上的不同点,做了一个简单的对比:对比项Databuscanal结论支持的

发表回复

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

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