C++过河卒问题
#include <iostream>
#include <cstring>
using namespace std;int board[20][20]; // 棋盘
int dp[20][20][20][20]; // 动态规划数组int main() {int x0, y0, x1, y1;cin >> x0 >> y0 >> x1 >> y1; // 输入卒的起点和终点memset(board, 0, sizeof(board)); // 初始化棋盘// 初始化动态规划数组memset(dp, 0, sizeof(dp));dp[x0][y0][0][0] = 1;for(int i = x0; i <= x1; i++) {for(int j = y0; j <= y1; j++) {if(board[i][j] == 1) continue; // 如果该点有障碍物则跳过if(i > x0) dp[i][j][i-x0][0] += dp[i-1][j][i-x0-1][0]; // 上方的状态转移if(j > y0) dp[i][j][0][j-y0] += dp[i][j-1][0][j-y0-1]; // 左方的状态转移}}cout << dp[x1][y1][x1-x0][y1-y0] << endl; // 输出方案数return 0;
}
其中,动态规划数组 dp[i][j][x][y] 表示从起点 (x0, y0) 到当前点 (i, j) ,沿途经过了 x 行、y 列,一共有多少种方案。初始状态为 dp[x0][y0][0][0] = 1,表示从起点出发,沿途未经过行或列的方案数为 1。
状态转移方程为:
其中,dp[i][j][x][y] = dp[i-1][j][x-1][y] (如果 i > x0 && board[i][j] != 1)+ dp[i][j-1][x][y-1] (如果 j > y0 && board[i][j] != 1)board[i][j]表示棋盘上点(i, j)是否有障碍物。如果该点有障碍物,则不能通过该点。最终,需要输出dp[x1][y1][x1-x0][y1-y0]。
相关文章:
C++过河卒问题
#include <iostream> #include <cstring> using namespace std;int board[20][20]; // 棋盘 int dp[20][20][20][20]; // 动态规划数组int main() {int x0, y0, x1, y1;cin >> x0 >> y0 >> x1 >> y1; // 输入卒的起点和终点memset(board,…...
【机器学习12】集成学习
1 集成学习分类 1.1 Boosting 训练基分类器时采用串行的方式, 各个基分类器之间有依赖。每一层在训练的时候, 对前一层基分类器分错的样本, 给予更高的权重。 测试时, 根据各层分类器的结果的加权得到最终结果。 1.2 Bagging …...
nodeJs基础笔记
title: nodeJs基础笔记 date: 2023-11-18 22:33:54 tags: 1. Buffer 1. 概念 Buffer 是一个类似于数组的 对象 ,用于表示固定长度的字节序列。 Buffer 本质是一段内存空间,专门用来处理 二进制数据 。 2. 特点 Buffer 大小固定且无法调整Buffer 性能…...
Skywalking流程分析_9(JDK类库中增强流程)
前言 之前的文章详细介绍了关于非JDK类库的静态方法、构造方法、实例方法的增强拦截流程,本文会详细分析JDK类库中的类是如何被增强拦截的 回到最开始的SkyWalkingAgent#premain try {/** 里面有个重点逻辑 把一些类注入到Boostrap类加载器中 为了解决Bootstrap类…...
矩阵的QR分解
矩阵的QR分解 GramSchmidt 设存在 B { x 1 , x 2 , … , x n } \mathcal{B}\left\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\right\} B{x1,x2,…,xn}在施密特正交化过程中 q 1 x 1 ∣ ∣ x 1 ∣ ∣ q_1\frac{x_1}{||x_1||} q1∣∣x1∣∣x1 q k …...
STL总结
STL vector 头文件<vector> 初始化,定义,定义长度,定义长度并且赋值,从数组中获取数据返回元素个数size()判断是否为空empty()返回第一个元素front()返回最后一个数back()删除最后一个数pop_back()插入push_back(x)清空clear()begin()end()使用s…...
资深测试总结,现在软件测试有未来吗?“你“的底气在哪里?
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、为什么会有 “…...
Scalable Exact Inference in Multi-Output Gaussian Processes
Orthogonal Instantaneous Linear Mixing Model TY are m-dimensional summaries,ILMM means ‘Instantaneous Linear Mixing Model’,OILMM means ‘Orthogonal Instantaneous Linear Mixing Model’ 辅助信息 作者未提供代码...
sqli-labs(Less-3)
1. 通过构造id1’ 和id1’) 和id1’)–确定存在注入 可知原始url为 id(‘1’) 2.使用order by 语句猜字段数 http://127.0.0.1/sqlilabs/Less-3/?id1) order by 4 -- http://127.0.0.1/sqlilabs/Less-3/?id1) order by 3 --3. 使用联合查询union select http://127.0.0.1…...
集合框架面试题
一、集合容器的概述 1. 什么是集合 集合框架:用于存储数据的容器。 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合框架都包含三大块内容: 对外的接口、接口的实现和对集合运算的算 法。 接口:表示集合的抽象数据…...
【LeetCode刷题日志】225.用队列实现栈
🎈个人主页:库库的里昂 🎐C/C领域新星创作者 🎉欢迎 👍点赞✍评论⭐收藏✨收录专栏:LeetCode 刷题日志🤝希望作者的文章能对你有所帮助,有不足的地方请在评论区留言指正,…...
【JavaScript】fetch 处理流式数据,实现类 chatgpt 对话
本文只包含最基础的请求后端大佬给得对话接口,大部分模型的传参是差不多的,核心还是如何处理 fetch 获取的流数据 import { defineStore } from pinia; import { ElMessage } from element-plus;type Role system | user | assistant; export interfac…...
收发电子邮件
电子邮件是Internet提供的又一个重要服务项目。早在1987年9月20日,中国首封电子邮件就是从北京经意大利向前联邦德国卡尔斯鲁厄大学发出的,在中国首次实现了与Internet的连接,使中国成为国际互联网大家庭中的一员。现在随着Internet的迅速发展…...
sql13(Leetcode570至少有5名直接下属的经理)
代码: 脑子记不住 语法全靠试.. # Write your MySQL query statement below select b.name from (select managerId,count(managerId) as numfrom Employeegroup by managerId ) a left join Employee b on a.managerIdb.id where a.num>5 and b.name is not N…...
15分钟,不,用模板做数据可视化只需5分钟
测试显示,一个对奥威BI软件不太熟悉的人来开发数据可视化报表,要15分钟,而当这个人去套用数据可视化模板做报表,只需5分钟! 数据可视化模板是奥威BI上的一个特色功能板块。用户下载后更新数据源,立即就能获…...
C 语言字符串函数
C 语言字符串函数 在本文中,您将学习使用诸如gets(),puts,strlen()等库函数在C中操作字符串。您将学习从用户那里获取字符串并对该字符串执行操作。 您通常需要根据问题的需要来操作字符串。大多数字符串操作都可以自定义方法完成ÿ…...
nvm安装详细教程(卸载旧的nodejs,安装nvm、node、npm、cnpm、yarn及环境变量配置)
文章目录 一、完全卸载旧的nodejs1、打开系统的控制面板,点击卸载程序,卸载nodejs(1)打开系统的控制面板,点击程序下的卸载程序(2)找到node.js,鼠标右击出现下拉框,点卸载…...
详细步骤记录:持续集成Jenkins自动化部署一个Maven项目
Jenkins自动化部署 提示:本教程基于CentOS Linux 7系统下进行 Jenkins的安装 1. 下载安装jdk11 官网下载地址:https://www.oracle.com/cn/java/technologies/javase/jdk11-archive-downloads.html 本文档教程选择的是jdk-11.0.20_linux-x64_bin.tar.g…...
Python学习(一)基础语法
文章目录 1. 入门1.1 解释器的作用1.2 下载1.3 基础语法输入输出语法与引号注释:变量: 数据类型与四则运算数据类型四则运算数据类型的查看type()数据类型的转换int()、int()、float() 流程控制格式化输出循环与遍历逻辑运算符list遍历字典dict遍历 跳出…...
【C刷题】day7
🎥 个人主页:深鱼~🔥收录专栏:【C】每日一练🌄欢迎 👍点赞✍评论⭐收藏 一、选择题 1、以下对C语言函数的有关描述中,正确的有【多选】( ) A: 在C语言中,一…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
