[动态规划] 完美覆盖
描述
一张普通的国际象棋棋盘,它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌,每张牌恰好覆盖棋盘上相邻的两个方格,即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么,是否能够把 32 张多米诺牌摆放到棋盘上,使得任何两张多米诺牌均不重叠,每张多米诺牌覆盖两个方格,并且棋盘上所有的方格都被覆盖住?我们把这样一种排列称为棋盘被多米诺牌完美覆盖。这是一个简单的排列问题,同学们能够很快构造出许多不同的完美覆盖。但是,计算不同的完美覆盖的总数就不是一件容易的事情了。不过,同学们 发挥自己的聪明才智,还是有可能做到的。
现在我们通过计算机编程对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。

任务
对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。
输入
一次输入可能包含多行,每一行分别给出不同的 n 值 ( 即 3 乘 n 棋盘的列数 )。当输入 -1 的时候结束。
n 的值最大不超过 30.
输出
针对每一行的 n 值,输出 3 乘 n 棋盘的不同的完美覆盖的总数。
样例输入
2 8 12 -1
样例输出
3 153 2131
解题分析
首先,由于多米诺牌本身占两个格子,所以如果完全覆盖的话,那么n一个要偶数,否则3乘上一个奇数会导致格子总数为奇数,这就矛盾了。
然后,我们可以明显地感知到,我们当前排列的结果与前面的排列是有一定关系的。我们先计算一个n=2的时候,这是最小的单元(n=1的时候很明显,不可能被完全覆盖,或者从n必须为偶数理解)。我们自己脑子里摆一摆,知道n=2的时候有三种摆法。现在我们设置一个数组dp,dp[i]表示n=i时的摆法。显然,dp[i]中有一部分摆法是3*dp[i-2]。但是这显然没有包括全部的情况。那我们还漏掉了哪些情况?
简单举个例子,有两种很重要的情况被我们忽略了。比如n=4的时候,如果我们只是计算3*dp[2],那实际上我们在n=2,3这两列可以横着放多米诺牌。这部分被我们忽略了。所以我们还需要考虑dp[i-4],即我们空出四列出来,然后计算dp[i-4]*2,然后保持这两列横着放,继续i-=2,因为我们刚刚使用了dp[i-4],这是没有考虑i-4和i-5列横着放并且i-3和i-2列横着放的情况。
代码实现
#include <iostream>
using namespace std;
int dp[31]={0};int compute(int m){if(dp[m]) return dp[m];for(int i=4;i<=30;i++){dp[i]=dp[i-2]*3;for(int j=i-4;j>=0;j-=2){dp[i]+=dp[j]*2;}}return dp[m];
}int main(){int n;dp[0]=1;dp[2]=3;while(cin>>n){if(n==-1){break; }cout<<compute(n)<<endl;}return 0;
}
相关文章:
[动态规划] 完美覆盖
描述 一张普通的国际象棋棋盘,它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌,每张牌恰好覆盖棋盘上相邻的两个方格,即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么,是否能够把 32 张多米诺牌摆放…...
redis深入理解之实战
1、SpringBoot整合redis 1.1 导入相关依赖 <dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId> </dependency> <dependency><groupId>org.springframework.boot</groupId><artifactId&g…...
python设计模式---工厂模式
定义了一个抽象类Animal,并且让具体的动物类(Dog、Cat、Duck)继承自它,并实现了speak方法。然后创建了AnimalFactory工厂类,根据传入的参数来决定创建哪种动物的实例。 from abc import abstractmethod, ABCclass Anim…...
探索Vue 3.0中的v-html指令
探索Vue 3.0中的v-html指令 一、什么是v-html指令?1、 在Vue 3.0中使用v-html2、 注意事项 二、结语 一、什么是v-html指令? Vue.js作为一款流行的JavaScript框架,不断地演进着。随着Vue 3.0的发布,开发者们迎来了更加强大和灵活…...
anaconda 环境配置
官方网站下载地址: https://www.anaconda.com/download/ 国内清华镜像下载地址: https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 配置国内环境: conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/ …...
DS:顺序表、单链表的相关OJ题训练(2)
欢迎各位来到 Harper.Lee 的学习世界! 博主主页传送门:Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦! 一、力扣--141. 环形链表 题目描述:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个…...
上传到 PyPI
将软件包上传到 PyPI(Python Package Index),您需要遵循以下步骤: 准备软件包:确保您的软件包满足以下要求: 包含一个 setup.py 文件,用于描述软件包的元数据和依赖项。包含软件包的源代码和必要…...
盛最多水的容器(双指针)
解题思路: 1,暴力解法(超时) 我们可以使用两层for循环进行遍历。找到那个最大的面积即可,这里我就不写代码了,因为写了也是超时。 2,双指针法 先定义两个指针一个在最左端,一个在…...
【深度学习】实验3 特征处理
特征处理 python 版本 3.7 scikit-learn 版本 1.0.2 1.标准化 from sklearn.preprocessing import StandardScaler from sklearn.preprocessing import MinMaxScaler from matplotlib import gridspec import numpy as np import matplotlib.pyplot as plt cps np.random.…...
MoneyPrinter国内版改造
背景: MoneyPrinter 是一个自动生成短视频的开源项目。只需要输入短视频主题,然后就可以生成视频。 在国内环境运行时,框架中使用的youtube、抖音文字转语音等功能无法使用,需要对框架进行国内版改造,使其使用国内网络…...
C++ 派生类的引入与特性
一 继承与派生 从上面的例子可以看出: 继承:一旦指定了某种事物父代的本质特征,那么它的子代将会自动具有哪些性质。这就是一种朴素的可重用的概念。 派生:而且子代可以拥有父代没有的特性,这是可扩充的概念。 1 C 的…...
Poe是什么?怎样订阅Poe?
Poe(全称“开放探索平台”,Platform for Open Exploration)是一款由Quora开发的移动应用程序,于2022年12月推出。该应用程序内置建基于AI技术的聊天机器人,可供用户向机器人询问专业知识、食谱、日常生活,甚…...
基于FPGA的视频矩阵切换方案
一、单个显示设备的系统方案:会议室只有1个显示设备 会议室的信号源有很多,但是显示设备只有1个,这个时候最佳方案是使用切换器。 (1)切换器(控制方式:遥控器、软件、机箱面板、中控ÿ…...
.NET周刊【5月第1期 2024-05-05】
国内文章 一个开源轻量级的C#代码格式化工具(支持VS和VS Code) https://www.cnblogs.com/Can-daydayup/p/18164905 CSharpier是一个开源、免费的C#代码格式化工具,特点是轻量级且依赖Roslyn引擎重构代码格式。支持的IDE包括Visual Studio …...
springcloud -nacos实战
一、nacos 功能简介 1.1.什么是Nacos? 官方简介:一个更易于构建云原生应用的动态服务发现(Nacos Discovery )、服务配置(Nacos Config)和服务管理平台。 Nacos的关键特性包括: 服务发现和服务健康监测动态配置服务动态DNS服务服务及其元数…...
第十五章 数据管理成熟度评估练习
单选题 (每题1分,共19道题) 1、 [单选] 下列选项中属于数据管理成熟度2级特征的选项是? A:很少或没有治理;有限的工具集;单个竖井(系统)内定义角色;控件(如果有的话的应用完全不一致);未解决的数据质量问题 B:治理开始出现;引入一致的工具集;定义了一些角色和…...
tcpdump速查表
tcpdump 速查表 -D 列出网络设备 ~]$ sudo tcpdump -D1.eth02.nflog (Linux netfilter log (NFLOG) interface)3.nfqueue (Linux netfilter queue (NFQUEUE) interface)4.any (Pseudo-device that captures on all interfaces)5.lo [Loopback]-i 指定网卡 前面列出的设备可以…...
单元测试与集成测试:软件质量的双重保障
目录 概述 单元测试 集成测试 单元测试的方法 白盒测试 黑盒测试 白盒测试的方法和用例设计 代码审查 集成测试 单元测试工具 结语 在软件开发中,测试是一个不可或缺的环节,它能够帮助我们发现和修复缺陷,确保软件的质量和可靠性。…...
孙宇晨对话大公网:香港Web3政策友好环境示范意义重大
日前,全球知名华文媒体大公网发布《湾区web3大有可为》重磅系列报道。报道通过对中国香港与大湾区其他城市Web3政策、行业创新和生态建设等方面的梳理,以及对行业领袖和重要行业机构的走访,全面展现了在大湾区一体化发展的背景下,Web3等数字经济模式在该地区的长远发展潜力。 …...
Python运维之多线程!!
一、多线程 二、多线程编程之threading模块 2.1、使用threading进行多线程操作有两种方法: 三、多线程同步之Lock(互斥锁) 四、多线程同步之Semaphore(信号量) 五、多线程同步之Condition 六、多线程同步之Event…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
Easy Excel
Easy Excel 一、依赖引入二、基本使用1. 定义实体类(导入/导出共用)2. 写 Excel3. 读 Excel 三、常用注解说明(完整列表)四、进阶:自定义转换器(Converter) 其它自定义转换器没生效 Easy Excel在…...
Element-Plus:popconfirm与tooltip一起使用不生效?
你们好,我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip,产品要求是两个需要结合一起使用,也就是鼠标悬浮上去有提示文字,并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起,为了跨网段推流,千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...
claude3.7高阶玩法,生成系统架构图,国内直接使用
文章目录 零、前言一、操作指南操作指导 二、提示词模板三、实战图书管理系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 在线考试系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 四、感受 零、前言 现在很多AI大模型可以…...
