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

垒骰子(爆搜/DP)

动态规划

    • 方格取数
    • 垒骰子

方格取数

题目描述

设有 N×NN \times NN×N 的方格图 (N≤9)(N \le 9)(N9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 000。如下图所示(见样例):

A0  0  0  0  0  0  0  00  0 13  0  0  6  0  00  0  0  0  7  0  0  00  0  0 14  0  0  0  00 21  0  0  0  4  0  00  0 15  0  0  0  0  00 14  0  0  0  0  0  00  0  0  0  0  0  0  0B

某人从图的左上角的 AAA 点出发,可以向下行走,也可以向右走,直到到达右下角的 BBB 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 000)。
此人从 AAA 点到 BBB 点共走两次,试找出 222 条这样的路径,使得取得的数之和为最大。

输入格式

输入的第一行为一个整数 NNN(表示 N×NN \times NN×N 的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的 000 表示输入结束。

输出格式

只需输出一个整数,表示 222 条路径上取得的最大的和。

样例 #1

样例输入 #1

8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0

样例输出 #1

67

在这里插入图片描述

注意这里需要分为 i和j 是否相等,如果不相等一定不在同一个格子中,那就可以取两次了,为什么可以优化成三维,是因为如果走的次数是固定的,横坐标和纵坐标的和事固定的(行数+列数)。
注意,有了步数这一实际意义(大于等于0)和 步数与行数之间的约束(后者必须小于前者),循环的嵌套顺序和行数循环终止条件要注意

#include <iostream>
using namespace std;
//#define int long long int
const int N=10;
int a[N][N];
int dp[N][N][N][N];
int n,x,y,s;
int get_max(int u,int v,int o,int p){return max(max(u,v),max(o,p));
}
signed main(int argc, char** argv) {cin>>n;while(cin>>x>>y>>s){if(!x&&!y&&!s)break;a[x][y]=s;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){for(int l=1;l<=n;l++){dp[i][j][k][l]=get_max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])+a[i][j]+a[k][l];
//			两个人一步有四种结果if(i==k&&j==l)dp[i][j][k][l]-=a[i][j];}}}}cout<<dp[n][n][n][n];return 0;
}
#include <iostream>
using namespace std;
//#define int long long int
const int N=10;
int a[N][N];
int dp[N][N][N*2];
int n,x,y,s;
int get_max(int u,int v,int o,int p){return max(max(u,v),max(o,p));
}
signed main(int argc, char** argv) {cin>>n;while(cin>>x>>y>>s){if(!x&&!y&&!s)break;a[x][y]=s;}dp[1][1][0]=a[1][1];//初始化for(int k=1;k<=(n-1)*2;k++){//已经走了多少步(两个人是同时走一步)for(int i=1;i<=min(k+1,n);i++){for(int j=1;j<=min(k+1,n);j++){dp[i][j][k]=get_max(dp[i-1][j][k-1],dp[i-1][j-1][k-1],dp[i][j][k-1],dp[i][j-1][k-1])+a[i][k+2-i]+a[j][k+2-j];
//			两个人一步有四种结果 p1向下p2向右,都向下,都向右,p1向右p2向下if(i==j)dp[i][j][k]-=a[i][k+2-i];
//			m行n列总共 m-1+n-1步
//			cx行,cx=i,cy列 cx-1+cy-1=k步 cy=k+2-cx	}}}cout<<dp[n][n][(n-1)*2];return 0;}
//1 1 1
//2 2 3 
//2 3 4

垒骰子

在这里插入图片描述

在这里插入图片描述
爆搜

#include <iostream>
using namespace std;
#define int long long int
const int mod=1e9+7;
const int N=10;
int m,n,x,y;
int back[7];
bool conflict[40][40];
int dfs(int u,int cnt){if(cnt==n+1){return 1;}int ans=0;for(int down=1;down<=6;down++){//枚举骰子底部的数字if(conflict[u][down])continue;ans=(ans+dfs(back[down],cnt+1))%mod;}
}
int quickpow(int b,int e){b%=mod;int res=1;while(e){if(e&1)res=res*b%mod;b=b*b%mod;e=e>>1;}return res;
}
signed main(int argc, char** argv) {back[1]=4;back[4]=1;back[2]=5;back[5]=2;back[3]=6;back[6]=3;cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;conflict[x][y]=true;conflict[y][x]=true;}int res=0;for(int down=1;down<=6;down++){res=(res+dfs(back[down],2))%mod;}res=res*quickpow(4,n)%mod;cout<<res;return 0;}

在这里插入图片描述
在这种解题方式上用快速幂有些多余。分枝过多的递归当n=100时,几乎不能在题目规定时间内计算出来。当n<100时,通过累乘的方式将4一次、一次乘给ans,这并不会对程序的效率造成很大影响。

相关文章:

垒骰子(爆搜/DP)

动态规划方格取数垒骰子方格取数 题目描述 设有 NNN \times NNN 的方格图 (N≤9)(N \le 9)(N≤9)&#xff0c;我们将其中的某些方格中填入正整数&#xff0c;而其他的方格中则放入数字 000。如下图所示&#xff08;见样例&#xff09;: A0 0 0 0 0 0 0 00 0 13 0 …...

Telink之标准SDK的介绍_1

前提&#xff1a;常见的项目架构&#xff1a;应用层----》驱动层----》硬件层 1、软件组织架构 顶层⽂件夹( 8 个)&#xff1a; algorithm&#xff0c;application&#xff0c;boot&#xff0c;common&#xff0c;drivers&#xff0c;proj_lib&#xff0c;stack&#xff0c;v…...

JNI内两种方式从C/C++中传递一维、二维、三维数组数据至Java层详细梳理

目录 0 前言 1 准备工作介绍 2 一维数组 2.1 return形式 2.2 参数形式 3 二维数组 3.1 return形式 3.2 参数形式 4 三维数组 4.1 return形式 4.2 参数形式 5 测试代码 6 结果说明 0 前言 就如之前我写过的一篇文章【JNI内形参从C代码中获取返回值并返回到Java层使…...

快递计费系统--课后程序(Python程序开发案例教程-黑马程序员编著-第3章-课后作业)

实例5&#xff1a;快递计费系统 快递行业高速发展&#xff0c;我们邮寄物品变得方便快捷。某快递点提供华东地区、华南地区、华北地区的寄件服务&#xff0c;其中华东地区编号为01、华南地区编号为02、华北地区编号为03&#xff0c;该快递点寄件价目表具体如表1所示。 表1 寄…...

JS - 自定义一周的开始和结束,计算日期所在月的周数、所在月第几周、所在周的日期范围

自定义一周的开始和结束&#xff0c;计算日期所在月的周数、所在月第几周、所在周的日期范围一. 方法使用二. 实现案例一. 方法使用 根据月开始日期星期几、月结束日期星期几&#xff0c;计算始周、末周占月的天数&#xff08;每周周期段&#xff1a;上周六 —— 本周五&#x…...

Linux :理解编译的四个阶段

目录一、了解编译二、认识编译的四个阶段&#xff08;一&#xff09;预处理&#xff08;二&#xff09;编译&#xff08;三&#xff09;汇编&#xff08;四&#xff09;链接1.静态链接2.动态链接三、分步编译&#xff08;一&#xff09;创建.c文件&#xff08;二&#xff09;预…...

197.Spark(四):Spark 案例实操,MVC方式代码编程

一、Spark 案例实操 1.数据准备 电商网站的用户行为数据,主要包含用户的 4 种行为:搜索,点击,下单,支付 样例类: 2. Top10 热门品类 先按照点击数排名,靠前的就排名高;如果点击数相同,再比较下单数;下单数再相同,就比较支付数。 我们有多种写法,越往后性能越…...

Vue 项目如何迁移小程序

最近我们看到有开发者在社群里提出新的疑惑「我手头已经有一个成熟的 HTML5 项目了&#xff0c;这种项目可以转为小程序在 FinClip 环境中运行吗&#xff1f;」。 经过工作人员的沟通了解&#xff0c;开发者其实是想将已有的 Vue 项目转为小程序&#xff0c;在集成了 FinClip …...

unit1-问候以及介绍

unit1-问候以及介绍 重点表达 1、问好 使用hello 和 hi 来打招呼。hello可以使用在正式和非正式的场合。hi是非正式的。但是hello 和 hi 都可以在一天的任何时段使用。 Hello. 你好。 Hi! 嗨&#xff01; 介绍你的姓名 使用 I’m 和 My name is 告诉别人你的名字。 I’m Pau…...

杂记——19.git上传时出现the remote end hung up unexpectedly错误

git是大家常用的项目版本控制工具&#xff0c;熟练地使用git可以提高开发效率&#xff0c;但是有时在使用git推送代码时&#xff0c;会提示“the remote end hung up unexpectedly”的问题&#xff0c;那么git推送代码提示“the remote end hung up unexpectedly”怎么解决呢&a…...

python123平台题目

作业二 1. 2的n次方描述输入格式输出格式输入输出实例代码解析2. 输出最大值描述输入格式输出格式输入输出示例代码解析3. 字符串输出描述输入格式输出格式输入输出示例代码解析4. 字符串长度描述输入格式输出格式输入输出示例代码解析...

ROS学习笔记(六):TF坐标变换

ROS学习笔记&#xff08;六&#xff09;&#xff1a;TF坐标变换TF的基本知识TF工具tf_monitortf_echostatic_transform_publisherview_frames创建TF广播器创建TF监听器TF的基本知识 TF是一个让用户随时间跟踪多个坐标系的功能包&#xff0c;它使用树形数据结构&#xff0c;根据…...

【python】为你绘制玫瑰一束,爱意永存

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 若是有真情&#xff0c;爱意如溪水&#xff0c; 若是有真爱&#xff0c;爱意如阳光&#xff0c; 若是两情相悦&#xff0c;又岂在朝朝暮暮&#xff0c; 女子淡淡的情愫&#xff0c;深深地想念&#xff0c; 浓浓的爱意&a…...

智能家居创意产品一Homkit智能通断器

智能通断器&#xff0c;也叫开关模块&#xff0c;可以非常方便地接入家中原有开关、插座、灯具、电器的线路中&#xff0c;通过手机App或者语音即可控制电路通断&#xff0c;轻松实现原有家居设备的智能化改造。 随着智能家居概念的普及&#xff0c;越来越多的人想将自己的家改…...

【数据库】MySQL表的增删改查(基础命令详解)

写在前面 : 语法中大写字母是关键字&#xff0c;用[]括这的是可以省略的内容。文中截图是相对应命令执行完得到的结果截图。1.CRUD 注释&#xff1a;在SQL中可以使用“--空格描述”来表示注释说明.CRUD:即增加(Create)、查询(Retrieve)、更新(Update)、删除(Delete)四个单词的首…...

2023年全国最新保安员精选真题及答案15

百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 151.该图所要表达的是&#xff08;&#xff09;消防器材。 A:地上消防栓 B:灭火器 …...

KPN对任意形状文本检测

文章目录一、研究背景二、方法流程1. 特征提取2. 核建议3. 实例无关特征图4. 轮廓生成5. 其余部分内容三、不足一、研究背景 相比起基于 FCN 网络的文本边缘检测网络&#xff0c;KPN网络可以更好地处理文本之间的间隔。 二、方法流程 1. 特征提取 FCN 和 FPN FCN(全卷积神经…...

同城外卖跑腿系统源码分析

外卖订餐已经成为很多“社畜”日常不可分割的一部分&#xff0c;足不出户&#xff0c;只需要一部电子设备即可在线订餐&#xff0c;并且可提供的选择非常多样化&#xff0c;与传统的电话订餐外卖模式相比也更便捷的多。 因此&#xff0c;同城外卖跑腿系统源码得以爆火&#xff…...

SCL_PFENET跑通填坑

1.数据准备&#xff1a;VOC2012数据集&#xff0c;initmodel文件夹&#xff08;预训练模型&#xff09;&#xff0c;SegmentationClassAug数据2.训练部分&#xff1a;训练部分没什么需要改动的&#xff0c;也就改一下选择的配置文件。在config文件夹里有关于coco和voc数据的配置…...

Redis 做延迟消息队列

背景 看到消息队列&#xff0c;我们肯定会想到各种MQ&#xff0c;比如&#xff1a;RabbitMQ&#xff0c;acivityMQ、RocketMQ、Kafka等。 但是&#xff0c;当我们需要使用消息中间件的时候&#xff0c;并非每次都需要非常专业的消息中间件&#xff0c;假如我们只有一个消息队…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...