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

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...