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

搜索+动态规划

刷题刷题刷题刷题

​​​​​​​​​​​​​​Forgery - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:

需要两个数组,一个数组全部初始化为".",另一个数组输入数据,每碰到一个“.”就进行染色操作,将其周围的8个全部变成"#",全部染完色之后将两个数组进行比对,若完全一样则YES,否则NO

AC代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
char a[1010][1010];
char b[1010][1010];
int n, m;
int flag;
bool cmp()
{for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (a[i][j] != b[i][j])return false;return true;
}
void dfs(int x, int y)
{flag = 1;int next[8][2] = { {1,1},{-1,-1},{-1,0},{1,0},{0,1},{0,-1},{1,-1},{-1,1} };for (int i = 0; i < 8; i++){int tx = x + next[i][0];int ty = y + next[i][1];if (tx<1 || ty<1 || tx>n || ty>m){flag = 0;return;}if (a[tx][ty] != '#'){flag = 0;break;}}if (!flag)return;for (int i = 0; i < 8; i++){int tx = x + next[i][0];int ty = y + next[i][1];b[tx][ty] = '#';}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){cin >> a[i][j];b[i][j] = '.';}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){dfs(i, j);}if (cmp())cout << "YES";else{cout << "NO";}return 0;
}

P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:

开始没写出来,看了题解后有了一些头绪(感觉应该有普及+的难度了)。

用数组记录需要种类数的最小量和不同饲料不同种类的最小量,

从第一种饲料开始进入搜索,每次搜索进行一次判断,若饲料数已超过数据则马上结束这一次搜索(对当前饲料进行搜索,用数组记录),得到需要的饲料数,并用数组存起来所需的饲料编号,对所有饲料的相同一种的维他命进行判断,得到最优解,继续进行搜索有两种可能(一是不算当前饲料,即饲料数加1,但是所需饲料数不加1,二是当前饲料数和所需饲料数都加1),最后所有搜索结束后按照题目要求输出即可

AC:

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int a[1010];
int b[1010][1010];
int ans[1010];
int n, m, k=20;
int s[1010];
bool judge(int x)
{for (int i = 1; i <= n; i++){int sum = 0;for (int j = 1; j <= x; j++){sum += b[s[j]][i];}if (sum < a[i])return false;}return true;
}
void dfs(int pos, int num)
{if (pos > m){if (judge(num) && num < k){k = num;for (int i = 1; i <=  num; i++){ans[i] = s[i];}}return;}s[num + 1] = pos;dfs(pos + 1, num + 1);dfs(pos + 1, num);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}cin >> m;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){cin >> b[i][j];}}dfs(1, 0);cout << k << " ";for (int i = 1; i <= k; i++)cout << ans[i] << " ";cout << endl;return 0;
}

01背包思路(太久远了,忘了)

来几道板子题唤醒一下沉睡的记忆

P1060 [NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

AC:

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int v[100010], w[100010];
int dp[1010][30010];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= m; i++){cin >> v[i] >> w[i];w[i] = w[i] * v[i];}for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (v[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}}}cout << dp[m][n];return 0;
}

P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

AC:

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int dp[35][20010];
int w[20010];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int v, n;cin >> v >> n;for (int i = 1; i <= n; i++){cin >> w[i];}for (int i = 1; i <= n; i++){for (int j = 1; j <= v; j++){if (w[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]]+w[i]);}}}cout << v-dp[n][v];return 0;
}

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int w[110];
int t[1100];
int dp[110][1100];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= m; i++){cin >> t[i] >> w[i];}for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (t[i] > j)dp[i][j] = dp[i - 1][j];else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + w[i]);}}}cout << dp[m][n];return 0;
}

分组背包问题(卡了半天也并不知道哪错了,无语)

P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int a[1010], b[1010], c[1010];
int dp[1010];
int g[1010][1010];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, t, x = 0;cin >> m >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> t;x = max(t, x);c[t]++;g[t][c[t]] = i;}for (int i = 1; i <= x; i++)//小组{for (int j = m; j >= 0; j--)//容量{for (int k = 1; k <= c[i]; k++)//小组成员{if(a[g[i][k]]<=j)dp[j] = max(dp[j], dp[j - a[g[i][k]]] + b[g[i][k]]);}}}cout << dp[m] << endl;return 0;
}

相关文章:

搜索+动态规划

刷题刷题刷题刷题 ​​​​​​​​​​​​​​Forgery - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路&#xff1a; 需要两个数组&#xff0c;一个数组全部初始化为".",另一个数组输入数据&#xff0c;每碰到一个“.”就进行染色操作&#xff0c;将其周围的…...

strcpy,srtcmp,strlen函数漏洞利用

strcpy,srtcmp,strlen函数漏洞利用 strcpy strcpy函数用于将字符串复制到另一个指针指向的空间中&#xff0c;遇到空字符 **b’x\00’**时停止&#xff0c;&#xff1a; 所以可以利用 strcpy不检查缓冲区 的漏洞&#xff08;构造的字符串要以\0结尾&#xff09;&#xff0c;…...

SketchUp + Enscape+ HTC Focus3 VR

1. 硬件: 设备连接 2. 软件: 安装steam steamVR Vive Business streaming 3. 操作: 双方登录steam 账号,然后带上头盔,用手柄在HTC Focus3 安装 串流软件,选择串流软件,在Enscape中选择 VR 模式即可 4.最终效果: SketchUp Enscape HTC Focus 3 VR 实时预览_哔哩哔哩_bi…...

推荐3款Windows系统的神级软件,免费、轻量、绝对好用!

DiskView DiskView是一款用于管理和查看磁盘空间的工具&#xff0c;它集成了于微软的Windows操作系统资源管理器中&#xff0c;以显示直观的磁盘空间使用情况。该软件通过生成图形化地图&#xff0c;帮助用户组织和管理大量文件和文件夹&#xff0c;从而高效地管理磁盘空间。用…...

-bash: /snap/bin/docker: 没有那个文件或目录

-bash: /snap/bin/docker: 没有那个文件或目录 解决办法 export PATH$PATH:/usr/bin/docker然后&#xff0c;重新加载配置文件 source ~/.bashrc...

[深度学习]卷积理解

单通道卷积 看这个的可视化就很好理解了 https://github.com/vdumoulin/conv_arithmetic/blob/master/README.md 多通道卷积 当输入有多个通道时,卷积核需要拥有相同的通道数. 假设输入有c个通道,那么卷积核的每个通道分别于相应的输入数据通道进行卷积,然后将得到的特征图对…...

基于aardio web.view2库和python playwright包的内嵌浏览器自动化操作

通过cdp协议可以实现playwright操控webview。 新建Python窗口工程 修改pip.aardio 修改pip.aardio&#xff0c;并执行&#xff0c;安装playwright。 //安装模块 import process.python.pip; //process.python.path "python.exe";/* 安装模块。 参数可以用一个字…...

《数据仓库与数据挖掘》 总复习

试卷组成 第一章图 第二章图 第三章图 第四章图 第五章图 第六章图 第九章图 第一章 DW与DM概述 &#xff08;特点、特性&#xff09; DB到DW 主要特征 &#xff08;1&#xff09;数据太多&#xff0c;信息贫乏&#xff08;Data Rich&#xff0c; Information Poor)。 &a…...

EtherCAT主站IGH-- 8 -- IGH之domain.h/c文件解析

EtherCAT主站IGH-- 8 -- IGH之domain.h/c文件解析 0 预览一 该文件功能`domain.c` 文件功能函数预览二 函数功能介绍1. `ec_domain_init`2. `ec_domain_clear`3. `ec_domain_add_fmmu_config`4. `ec_domain_add_datagram_pair`5. `ec_domain_finish`6. `ecrt_domain_reg_pdo_en…...

《昇思25天学习打卡营第10天|使用静态图加速》

文章目录 今日所学&#xff1a;一、背景介绍1. 动态图模式2. 静态图模式 三、静态图模式的使用场景四、静态图模式开启方式1. 基于装饰器的开启方式2. 基于context的开启方式 总结&#xff1a; 今日所学&#xff1a; 在上一集中&#xff0c;我学习了保存与加载的方法&#xff…...

【HarmonyOS4学习笔记】《HarmonyOS4+NEXT星河版入门到企业级实战教程》课程学习笔记(二十二)

课程地址&#xff1a; 黑马程序员HarmonyOS4NEXT星河版入门到企业级实战教程&#xff0c;一套精通鸿蒙应用开发 &#xff08;本篇笔记对应课程第 32 节&#xff09; P32《31.通知-基础通知》 基础文本类型通知&#xff1a;briefText 没有用&#xff0c;写了也白写。 长文本类型…...

六西格玛绿带培训如何告别“走过场”?落地生根

近年来&#xff0c;六西格玛绿带培训已经成为了众多企业提升管理水平和员工技能的重要途径。然而&#xff0c;不少企业在实施六西格玛绿带培训时&#xff0c;往往陷入形式主义的泥潭&#xff0c;导致培训效果大打折扣。那么&#xff0c;如何避免六西格玛绿带培训变成“走过场”…...

Linux——提取包文件到指定目录,命令解释器-shell,type 命令

- 提取包文件到指定目录 bash tar xf/-xf/-xzf 文件名.tar.gz [-C 目标路径] tar xf/-xf/-xjf 文件名.tar.bz2 [-C 目标路径] tar xf/-xf/-xJf 文件名.tar.xz [-C 目标路径] ### 示例 - 将/etc下所有内容打包压缩到/root目录中 bash [rootserver ~]# tar -cvf taretc…...

【最详细】PhotoScan(MetaShape)全流程教程

愿天下心诚士子&#xff0c;人人会PhotoScan&#xff01; 愿天下惊艳后辈&#xff0c;人人可剑开天门&#xff01; 本教程由CSDN用户CV_X.Wang撰写&#xff0c;所用数据均来自山东科技大学视觉测量研究团队&#xff0c;特此鸣谢&#xff01;盗版必究&#xff01; 一、引子 Ph…...

Excel多表格合并

我这里一共有25张表格: 所有表的表头和格式都一样,但是内容不一样: 现在我要做的是把所有表格的内容合并到一起,研究了一下发现WPS的这项功能要开会员的,本来想用代码撸出来的,但是后来想想还是找其他办法,后来找到"易用宝"这个插件,这个插件可以从如下地址下载:ht…...

AI作画工具深度剖析:Midjourney vs. Stable Diffusion (SD)

在人工智能技术的推动下&#xff0c;艺术创作的边界被不断拓宽&#xff0c;AI作画工具成为数字艺术家与创意人士的新宠。其中&#xff0c;Midjourney与Stable Diffusion&#xff08;SD&#xff09;作为当前领域的佼佼者&#xff0c;以其独特的算法机制、丰富的功能特性及高质量…...

ASP.NET Core Blazor 5:Blazor表单和数据

本章将描述 Blazor 为处理 HTML 表单提供的特性&#xff0c;包括对数据验证的支持。 1 准备工作 继续使用上一章项目。   创建 Blazor/Forms 文件夹并添加一个名为 EmptyLayout.razor 的 Razor 组件。本章使用这个组件作为主要的布局。 inherits LayoutComponentBase<div …...

C++ 仿QT信号槽二

// 实现原理 // 每个signal映射到bitset位&#xff0c;全集 // 每个slot做为signal的bitset子集 // signal全集触发&#xff0c;标志位有效 // flip将触发事件队列前置 // slot检测智能指针全集触发的标志位&#xff0c;主动运行子集绑定的函数 // 下一帧对bitset全集进行触发清…...

联合概率密度函数

目录 1. 什么是概率密度由联合概率密度求概率参考链接 1. 什么是概率密度 概率密度到底在表达什么&#xff1f; 外卖在20-40分钟内送达的概率 随机变量落在[20,40]之间的概率。下图中&#xff0c;对总面积做规范化处理&#xff0c;令总面积1&#xff0c; f ( x ) f(x) f(x)则成…...

【Java10】成员变量与局部变量

Java中的变量只有两种&#xff1a;成员变量和局部变量。 和C不同&#xff0c;没有全局变量了。 成员变量&#xff0c;field&#xff0c;我习惯称之为**”属性“**&#xff08;但这些年&#xff0c;因为attribute更适合被叫做属性&#xff0c;所以渐渐不这么叫了&#xff09;。 …...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

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

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

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...