搜索+动态规划

刷题刷题刷题刷题

​​​​​​​​​​​​​​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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/775292.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Django学习第五天

Django学习第五天

启动项目命令 python manage.py runserver 图像验证码生成随机字母或者数字 import random from PIL import Image, ImageDraw, ImageFont, ImageFilterdef check_code(width120, height40, char_length5, font_fileZixunHappyBold.ttf, font_size28):code []img Image.new…
阅读更多...
在C#/Net中使用Mqtt

在C#/Net中使用Mqtt

net中MQTT的应用场景 c#常用来开发上位机程序&#xff0c;或者其他一些跟设备打交道比较多的系统&#xff0c;所以会经常作为拥有数据的终端&#xff0c;可以用来采集上传数据&#xff0c;而MQTT也是物联网常用的协议&#xff0c;所以下面介绍在C#开发中使用MQTT。 安装MQTTn…
阅读更多...
【ARMv8/v9 GIC 系列 5.1 -- GIC GICD_CTRL Enable 1 of N Wakeup Function】

【ARMv8/v9 GIC 系列 5.1 -- GIC GICD_CTRL Enable 1 of N Wakeup Function】

请阅读【ARM GICv3/v4 实战学习 】 文章目录 GIC Enable 1 of N Wakeup Function基本原理工作机制配置方式应用场景小结GIC Enable 1 of N Wakeup Function 在ARM GICv3（Generic Interrupt Controller第三代）规范中，引入了一个名为"Enable 1 of N Wakeup"的功能。…
阅读更多...
图像的对数变换

图像的对数变换

对数变换在图像处理中通常有以下作用&#xff1a; 因为对数曲线在像素值较低的区域斜率较大&#xff0c;像素值较高的区域斜率比较低&#xff0c;所以图像经过对数变换之后&#xff0c;在较暗的区域对比度将得到提升&#xff0c;因而能增强图像暗部的细节。图像的傅里叶频谱其…
阅读更多...
Ubuntu多显示器设置不同缩放比例

Ubuntu多显示器设置不同缩放比例

Ubuntu多显示器设置不同缩放比例 设备问题解决方案 设备 笔记本屏幕分辨率为2560 \times 1600&#xff0c;外接显示器的分辨率为3840 \times 2160。 问题 Ubuntu默认的显示器设置中&#xff0c;缩放仅能选择100%&#xff0c;200%&#xff0c;300%&#xff0c;400%。假…
阅读更多...
C++中的引用——引用做函数参数

C++中的引用——引用做函数参数

作用&#xff1a;函数传参时&#xff0c;可以利用引用的技术让形参修饰实参 优点&#xff1a;可以简化指针修改实参 示例&#xff1a; 1.值传递 运行结果&#xff1a; 2.地址传递 运行结果&#xff1a; 3.引用传递 运行结果&#xff1a;
阅读更多...
ES6模块化学习

ES6模块化学习

1. 回顾&#xff1a;node.js 中如何实现模块化 node.js 遵循了 CommonJS 的模块化规范。其中&#xff1a; 导入其它模块使用 require() 方法 模块对外共享成员使用 module.exports 对象 模块化的好处&#xff1a; 大家都遵守同样的模块化规范写代码&#xff…
阅读更多...
一对一服务，定制化小程序：NetFarmer助力企业精准触达用户

一对一服务，定制化小程序：NetFarmer助力企业精准触达用户

在当今这个日新月异的数字化时代&#xff0c;小程序以其独特的魅力和广泛的应用场景&#xff0c;正逐步成为企业出海战略中的璀璨明星。NetFarmer&#xff0c;作为业界领先的数字化出海服务商&#xff0c;不仅深谙HubSpot营销自动化的精髓&#xff0c;更在小程序领域展现了卓越…
阅读更多...
【UE5.3】笔记8 添加碰撞，检测碰撞

【UE5.3】笔记8 添加碰撞，检测碰撞

添加碰撞 打开BP_Food,添加Box Collision组件&#xff0c;与unity类似&#xff1a; 调整Box Collision的大小到刚好包裹物体&#xff0c;通过调整缩放和盒体范围来控制大小&#xff0c;一般先调整缩放找个大概大小&#xff0c;然后调整盒体范围进行微调。 碰撞检测 添加好碰撞…
阅读更多...
CTF常用sql注入（二）报错注入（普通以及双查询）

CTF常用sql注入（二）报错注入（普通以及双查询）

0x05 报错注入 适用于页面无正常回显&#xff0c;但是有报错&#xff0c;那么就可以使用报错注入 基础函数 floor() 向下取整函数 返回小于或等于传入参数的最大整数。换句话说&#xff0c;它将数字向下取整到最接近的整数值。 示例&#xff1a; floor(3.7) 返回 3 floor(-2…
阅读更多...
Python脚本：将Word文档转换为Excel文件

Python脚本：将Word文档转换为Excel文件

引言 在文档处理中&#xff0c;我们经常需要将Word文档中的内容转换成其他格式&#xff0c;如Excel&#xff0c;以便更好地进行数据分析和报告。针对这一需求&#xff0c;我编写了一个Python脚本&#xff0c;能够批量处理指定目录下的Word文档&#xff0c;将其内容结构化并转换…
阅读更多...
pandas，dataframe使用笔记

pandas，dataframe使用笔记

目录 新建一个dataframe不带列名带列名 dataframe添加一行内容查看dataframe某列的数据类型新建dataframe时设置了列名&#xff0c;则数据类型为object dataframe的保存保存为csv文件保存为excel文件 dataframe属于pandas 新建一个dataframe 不带列名 df pd.DataFrame() 带…
阅读更多...
【C++】unordered系列容器的封装

【C++】unordered系列容器的封装

你很自由 充满了无限可能 这是很棒的事 我衷心祈祷你可以相信自己 无悔地燃烧自己的人生 -- 东野圭吾 《解忧杂货店》 unordered系列的封装 1 unordered_map 和 unordered_set2 改造哈希桶2.1 模版参数2.2 加入迭代器 3 上层封装3.1 unordered_set3.2 unordered_map 4 面…
阅读更多...
C++基础22 字符串与字符数组及其相关操作

C++基础22 字符串与字符数组及其相关操作

这是《C算法宝典》C基础篇的第22节文章啦~ 如果你之前没有太多C基础&#xff0c;请点击&#x1f449;C基础&#xff0c;如果你C语法基础已经炉火纯青&#xff0c;则可以进阶算法&#x1f449;专栏&#xff1a;算法知识和数据结构&#x1f449;专栏&#xff1a;数据结构啦 ​ 目…
阅读更多...
c++重定向输出和输出（竞赛讲解）

c++重定向输出和输出（竞赛讲解）

1.命令行重定向 在命令行中指定输出文件 指令 .\重定向学习.exe > 1.txt 效果 命令行输入和输出 指令 .\重定向学习.exe < 2.txt > 1.txt 效果 代码 #include<bits/stdc++.h> using namespace std; int n; int main(){cin>>n;for(int i=0;i<n;i…
阅读更多...
4、SSD主控

4、SSD主控

简述 主控是个片上系统&#xff0c;由硬件和固件组成一个功能完整的系统&#xff1b;上文所述的FTL就属于主控的固件范畴。主控闪存构成了整个SSD&#xff0c;在闪存确定的情况下&#xff0c;主控就反映了各家SSD的差异。实时上各家SSD的差异也主要反应在主控上&#xff0c;毕…
阅读更多...
VMware虚拟机Ubuntu网络有线线缆已拔出问题

VMware虚拟机Ubuntu网络有线线缆已拔出问题

1、问题描述 VMware虚拟机Ubuntu不能联网&#xff0c;打开设置中&#xff0c;网络显示“有线 线缆已拔出”。 2、查看虚拟网络连接 查看主机的网络连接&#xff0c;确保虚拟网络已启用。 3、启动虚拟机网络服务 打开主机的 ‘服务’&#xff08;winr&#xff0c;运行框中输入…
阅读更多...
46.修复HOOK对代码造成的破坏

46.修复HOOK对代码造成的破坏

上一个内容&#xff1a;45.使用hook点链表实现指定跳转 以 45.使用hook点链表实现指定跳转 它的代码为基础进行修改 此代码已实现无敌与秒杀功能 HOOKPOINT.h文件里的修改 #pragma oncetypedef struct CPUINFO {unsigned eflags;unsigned edi;unsigned esi;unsigned ebp;un…
阅读更多...
PCL从理解到应用【03】KDTree 原理分析 | 案例分析 | 代码实现

PCL从理解到应用【03】KDTree 原理分析 | 案例分析 | 代码实现

前言 本文分析KDTree的原理&#xff0c;集合案例深入理解&#xff0c;同时提供源代码。 三个案例&#xff1a;K近邻搜索、半径内近邻搜索、近似最近邻搜索。方法对比&#xff0c;如下表所示&#xff1a; 特性K近邻搜索半径内近邻搜索近似最近邻搜索描述查找K个最近邻点查找指…
阅读更多...
Linux系统(CentOS)安装Mysql5.7.x

Linux系统(CentOS)安装Mysql5.7.x

安装准备&#xff1a; Linux系统(CentOS)添加防火墙、iptables的安装和配置 请访问地址&#xff1a;https://blog.csdn.net/esqabc/article/details/140209894 1&#xff0c;下载mysql安装文件&#xff08;mysql-5.7.44为例&#xff09; 选择Linux通用版本64位&#xff08;L…
阅读更多...
最新文章

Copyright @ 2022~2023