当前位置: 首页 > 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;假如我们只有一个消息队…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...