当前位置: 首页 > news >正文

[动态规划] 完美覆盖

描述

一张普通的国际象棋棋盘,它被分成 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;
}

相关文章:

[动态规划] 完美覆盖

描述 一张普通的国际象棋棋盘&#xff0c;它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌&#xff0c;每张牌恰好覆盖棋盘上相邻的两个方格&#xff0c;即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么&#xff0c;是否能够把 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&#xff0c;并且让具体的动物类&#xff08;Dog、Cat、Duck&#xff09;继承自它&#xff0c;并实现了speak方法。然后创建了AnimalFactory工厂类&#xff0c;根据传入的参数来决定创建哪种动物的实例。 from abc import abstractmethod, ABCclass Anim…...

探索Vue 3.0中的v-html指令

探索Vue 3.0中的v-html指令 一、什么是v-html指令&#xff1f;1、 在Vue 3.0中使用v-html2、 注意事项 二、结语 一、什么是v-html指令&#xff1f; Vue.js作为一款流行的JavaScript框架&#xff0c;不断地演进着。随着Vue 3.0的发布&#xff0c;开发者们迎来了更加强大和灵活…...

anaconda 环境配置

官方网站下载地址&#xff1a; https://www.anaconda.com/download/ 国内清华镜像下载地址&#xff1a; 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 的学习世界&#xff01; 博主主页传送门&#xff1a;Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦&#xff01; 一、力扣--141. 环形链表 题目描述&#xff1a;给你一个链表的头节点 head &#xff0c;判断链表中是否有环。如果链表中有某个…...

上传到 PyPI

将软件包上传到 PyPI&#xff08;Python Package Index&#xff09;&#xff0c;您需要遵循以下步骤&#xff1a; 准备软件包&#xff1a;确保您的软件包满足以下要求&#xff1a; 包含一个 setup.py 文件&#xff0c;用于描述软件包的元数据和依赖项。包含软件包的源代码和必要…...

盛最多水的容器(双指针)

解题思路&#xff1a; 1&#xff0c;暴力解法&#xff08;超时&#xff09; 我们可以使用两层for循环进行遍历。找到那个最大的面积即可&#xff0c;这里我就不写代码了&#xff0c;因为写了也是超时。 2&#xff0c;双指针法 先定义两个指针一个在最左端&#xff0c;一个在…...

【深度学习】实验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国内版改造

背景&#xff1a; MoneyPrinter 是一个自动生成短视频的开源项目。只需要输入短视频主题&#xff0c;然后就可以生成视频。 在国内环境运行时&#xff0c;框架中使用的youtube、抖音文字转语音等功能无法使用&#xff0c;需要对框架进行国内版改造&#xff0c;使其使用国内网络…...

C++ 派生类的引入与特性

一 继承与派生 从上面的例子可以看出&#xff1a; 继承&#xff1a;一旦指定了某种事物父代的本质特征&#xff0c;那么它的子代将会自动具有哪些性质。这就是一种朴素的可重用的概念。 派生&#xff1a;而且子代可以拥有父代没有的特性&#xff0c;这是可扩充的概念。 1 C 的…...

Poe是什么?怎样订阅Poe?

Poe&#xff08;全称“开放探索平台”&#xff0c;Platform for Open Exploration&#xff09;是一款由Quora开发的移动应用程序&#xff0c;于2022年12月推出。该应用程序内置建基于AI技术的聊天机器人&#xff0c;可供用户向机器人询问专业知识、食谱、日常生活&#xff0c;甚…...

基于FPGA的视频矩阵切换方案

一、单个显示设备的系统方案&#xff1a;会议室只有1个显示设备 会议室的信号源有很多&#xff0c;但是显示设备只有1个&#xff0c;这个时候最佳方案是使用切换器。 &#xff08;1&#xff09;切换器&#xff08;控制方式&#xff1a;遥控器、软件、机箱面板、中控&#xff…...

.NET周刊【5月第1期 2024-05-05】

国内文章 一个开源轻量级的C#代码格式化工具&#xff08;支持VS和VS Code&#xff09; https://www.cnblogs.com/Can-daydayup/p/18164905 CSharpier是一个开源、免费的C#代码格式化工具&#xff0c;特点是轻量级且依赖Roslyn引擎重构代码格式。支持的IDE包括Visual Studio …...

springcloud -nacos实战

一、nacos 功能简介 1.1.什么是Nacos&#xff1f; 官方简介&#xff1a;一个更易于构建云原生应用的动态服务发现(Nacos Discovery )、服务配置(Nacos Config)和服务管理平台。 Nacos的关键特性包括&#xff1a; 服务发现和服务健康监测动态配置服务动态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 指定网卡 前面列出的设备可以…...

单元测试与集成测试:软件质量的双重保障

目录 概述 单元测试 集成测试 单元测试的方法 白盒测试 黑盒测试 白盒测试的方法和用例设计 代码审查 集成测试 单元测试工具 结语 在软件开发中&#xff0c;测试是一个不可或缺的环节&#xff0c;它能够帮助我们发现和修复缺陷&#xff0c;确保软件的质量和可靠性。…...

孙宇晨对话大公网:香港Web3政策友好环境示范意义重大

日前,全球知名华文媒体大公网发布《湾区web3大有可为》重磅系列报道。报道通过对中国香港与大湾区其他城市Web3政策、行业创新和生态建设等方面的梳理,以及对行业领袖和重要行业机构的走访,全面展现了在大湾区一体化发展的背景下,Web3等数字经济模式在该地区的长远发展潜力。 …...

Python运维之多线程!!

一、多线程 二、多线程编程之threading模块 2.1、使用threading进行多线程操作有两种方法&#xff1a; 三、多线程同步之Lock&#xff08;互斥锁&#xff09; 四、多线程同步之Semaphore&#xff08;信号量&#xff09; 五、多线程同步之Condition 六、多线程同步之Event…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...