洛谷 P1722 矩阵 II C语言 记忆化搜索

news/2024/11/28 18:35:49/

题目:

https://www.luogu.com.cn/problem/P1722

我们按照案例画一下

我们会发现,会出现重复的子结构。

代码如下:

#include<iostream>
using namespace std;
int mem[300][300];
int n;
int f[305][305]; 
int dfs(int x,int red,int black)//x为当前格子数量,red,black分别表示为红球和黑球的数量 
{if(black > red || red > n)return 0;if(x == 2*n){if(red == n)return 1;elsereturn 0;}if(mem[red][black])return mem[red][black];int t = 0;t = (dfs(x+1,red+1,black)+dfs(x+1,red,black+1))%100; mem[red][black] = t;return t;
}
int main(void)
{cin >> n;int ans = dfs(0,0,0);cout << ans;return 0; 
}

动态规划:

#include<iostream>
using namespace std;
int n;
int f[305][305]; 
int main(void)
{cin >> n;//可以转化成有当前有i个格子有几个红色球 f[i][red]af[1][1] = 1;for(int i = 2 ; i <= 2*n ; i++){for(int red = (i+1)/2 ; red <= i; red++){f[i][red] = (f[i-1][red-1] + f[i-1][red])%100;}}cout << f[2*n][n];return 0; 
}

红球的范围是生成可能和不可能的答案,但是动态规划是选择最优子结构,会筛选不可能的答案,并且不能能的答案值是0.


http://www.ppmy.cn/news/1550691.html

相关文章

20241124 Typecho 视频插入插件

博文免不了涉及到视频插入这些,网上的插件都或多或少的比较重,和Typecho的风格不搭配 后面就有了DPlay插件精简而来的VideoInsertion插件 VideoInsertion: Typecho 视频插入插件 目录结构 rockhinlink-ht2:/var/www/html/typecho/usr/plugins/VideoInsertion$ tree -h [4.…

详解Qt之QCache 高速缓存

文章目录 QCache 详解前言什么是 QCache&#xff1f;什么是 LRU 策略&#xff1f;QCache 的构造函数和常用成员函数构造函数1. 默认构造函数2. 指定容量的构造函数 常用成员函数1. insert2. object3. contains4. remove5. clear6. setMaxCost 完整示例代码总结 QCache 详解 前…

【Linux】网络连接模式,VM:桥接、NAT、仅主机如何选择?

1、网络类型 虚拟机建立时的常见网络类型有3种&#xff1a;桥接、NAT&#xff08;Network Address Translation&#xff0c;网络地址转换&#xff09;、仅主机&#xff08;Host Only&#xff09; 桥接&#xff1a;VM直接连接路由器&#xff0c;与物理机地位相同&#xff1b;N…

D81【 python 接口自动化学习】- python基础之HTTP

day81 requests请求session用法 学习日期&#xff1a;20241127 学习目标&#xff1a;http定义及实战 -- requests请求session用法 学习笔记&#xff1a; requests请求session用法 import requests# 创建一个会话 reqrequests.session() url "http://sellshop.5istud…

ES 基本使用与二次封装

概述 基本了解 Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;基于 Apache Lucene 构建。它提供了对海量数据的快速全文搜索、结构化搜索和分析功能&#xff0c;是目前流行的大数据处理工具之一。主要特点即高效搜索、分布式存储、拓展性强 核心功能 全文搜索:…

Maven Surefire 插件简介

Maven Surefire 插件是 Maven 构建系统中的一个关键组件&#xff0c;专门用于在构建生命周期中执行单元测试。 它通常与 Maven 构建生命周期的测试阶段绑定&#xff0c;确保所有单元测试在项目编译后和打包前被执行。 最新版本 Maven Surefire 插件的最新版本为 3.5.2。 使…

【大数据学习 | Spark-SQL】SparkSQL读写数据

我们使用sparksql进行编程&#xff0c;编程的过程我们需要创建dataframe对象&#xff0c;这个对象的创建方式我们是先创建RDD然后再转换rdd变成为DataFrame对象。 但是sparksql给大家提供了多种便捷读取数据的方式。 //原始读取数据方式 sc.textFile().toRDD sqlSc.createDat…

Stable Diffusion 3详解

&#x1f33a;系列文章推荐&#x1f33a; 扩散模型系列文章正在持续的更新&#xff0c;更新节奏如下&#xff0c;先更新SD模型讲解&#xff0c;再更新相关的微调方法文章&#xff0c;敬请期待&#xff01;&#xff01;&#xff01;&#xff08;本文及其之前的文章均已更新&…