精确二分查找/上下取整

精确的二分查找 思路 * 第一个就是返回true 和 false 的精确查找,稍微改动即可实现查找 * C++里面有lower_bound(),upper_bound() 实现上取整下取整的,本文的第二个、第三个函数就是等价于这两个函数的 具体代码 先提供main和头文件等(下面的二分和这里的main是些一个文件里的) #include using namespace std; const int MAXN=1000; //设好一个最大长度,可以更改 int n,m,a[MAXN]; //n为长度,m为要查找的数 //下面放函数区 //上面     阅读全文
LittleBlack's avatar
LittleBlack 7月 03, 2019

Dynamic Programming

本文转载自 HankingHu 前言 最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间,查找了相关的文献和资料准备彻底的理解动态规划(Dynamic Programming)算法。一是帮助自己总结知识点,二是也能够帮助他人更好的理解这个算法。后面的参考文献只是我看到的文献的一部分。 动态规划算法的核心 理解一个算法就要理解一个算法的核心,动态规划算法的核心是下面的一张图片和一个小故事。 A * "1+     阅读全文
LittleBlack's avatar
LittleBlack 3月 23, 2019

OJ 1775:采药

本文转载自年糕踩过の坑 (动态规划)1775:采药 描述 辰辰是个很有潜能、天资聪颖的孩子,他的梦想是称为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。” 如果你是辰辰,你能完成这个任务吗? 输入 输入的第一行有两个整数T(1     阅读全文
LittleBlack's avatar
LittleBlack 3月 23, 2019

OJ 1944

1944:吃糖果 描述 名名的妈妈从外地出差回来,带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力,20 > N >0)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力,问名名共有多少种不同的吃完巧克力的方案。例如:如果N=1,则名名第1天就吃掉它,共有1种方案;如果N=2,则名名可以第1天吃1块,第2天吃1块,也可以第1天吃2块,共有2种方案;如果N=3,则名名第1天可以吃1块,剩2块,也可以第1天吃2块剩1块,所以名名共有2+1=3种方案;如果N=4,则名名可以第1天吃1块,剩3块,也可以第1天吃2块,剩2块,共有3+2=5种方案。现在给定N,请你写程序求出名名吃     阅读全文
LittleBlack's avatar
LittleBlack 2月 24, 2019

洛谷P1091题解

题目 分析 * 这题是一个动态规划中的LIS问题(最长上升子序列) * 题目将问题包装了一下,但思路还是清晰的 1. 先正着来一遍dp,将结果存到dp1数组内(找到最长上升子序列) 2. 再倒着来一遍dp,将结果存在dp2数组内(找到最长下降子序列) 3. 接着枚举两个dp,得到答案(一个交叉点使两个序列内元素最多) 代码 #include using namespace std; const int maxn = 105; //稍微开的比题目大一点 int dp1[maxn]; //dp1[     阅读全文
LittleBlack's avatar
LittleBlack 1月 27, 2019

OJ 8207

07:和为给定数 题目 * 描述 给出若干个整数,询问其中是否有一对数的和等于给定的数。 * 输入 共三行: 第一行是整数n(0 < n     阅读全文
LittleBlack's avatar
LittleBlack 1月 27, 2019

OJ 8209

06:月度开销 题解 估计有一大波人一拨人没有看懂意思,下面举例解释一下~ 就比如说我有4天,分成2份 4 2 100 500 300 200 那么正解应该这样分 //注意不存在顺序 (1) 第一个月:100 500 //600 第二个月:300 200 //500 或者是 (2) 第一个月:100 200 300 //600 第二个月:500 //500 所以答案是600,为什么呢 注意看(1),这两个月中开销最大的一个月是第一个600。而如果是其他的分法的话: (3) 第一个月:100 300 //400 第二个月:200 500 //700 这两个月的最大值是第二个月     阅读全文
LittleBlack's avatar
LittleBlack 1月 27, 2019