coder-River
coder-River
全部文章
分类
归纳(12)
题解(82)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
TA的专栏
98篇文章
0人订阅
Re:从零开始的刷题生活
85篇文章
858人学习
Re:从零开始的归纳时间
13篇文章
1067人学习
全部文章
(共94篇)
[贪心算法] 区间问题归纳
来自专栏
基本定义 区间用一个结构体来表示: struct Internal { int l, r; bool operator < (const Internal& rhs) const { return ......; // 按左端点 或 右端点 或其它排...
2020-09-04
1
481
Hdu 1059 背包问题 之 进来复习多重背包问题
来自专栏
一、题意 有6堆石头,第i堆石头中每个石头的价值都是i。然后输入每堆石头的数量num[i]。要求你判断是否可以将所有石头分成总价值相等的两堆。 二、解析 首先算出所有石头的总价值V,若V为奇数,则无解。若V为偶数,则我们的目标就是拿一个体积为V/2的背包,然后尽可能装满它。若装得满,说明原问题可以分...
2020-09-03
0
560
Hdu 4508 背包问题 之 复习一下完全背包问题
来自专栏
一、题意 输入包含多组测试用例。每组数据以一个整数n开始,表示每天的食物清单有n种食物。接下来n行,每行两个整数a和b,其中a表示这种食物可以带给湫湫的幸福值(数值越大,越幸福),b表示湫湫吃这种食物会吸收的卡路里量。最后是一个整数m,表示湫湫一天吸收的卡路里不能超过m。输出最大幸福值。 二、解析 ...
2020-09-03
0
623
Uva 624 背包问题 之 复习一下01背包问题
来自专栏
一、题意 给一个V(V<=10000)和一个n(n<=20),V代表磁带的最大长度,n表示n首曲子,然后给出每首曲子的长度,现在要求你选一些曲子放入磁带中,使得磁带的利用率最高,输出最终磁带中存放的曲子序列,并输出总长度。 二、解析 换了个皮也得认出这是一个01背包问题。翻译过来就是:往...
2020-09-03
0
719
Uva 116 动态规划 之 多阶段决策性问题 与 通过递归打印路径
来自专栏
一、题意 给一个n行m列的整数矩阵(n<=10, m<=100),从第一列的任何一个位置出发,每次可以往→、↗、↘走一格,最终到达最后一列。矩阵时环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行。现在要你找一条路线使得经过的数字之和最小。打印出路径和最小和。若有多解则输出字典...
2020-09-03
0
446
Uva 674 动态规划 之 刷表法解决找钱问题
来自专栏
一、题意 给定金额n,有50, 25, 10, 5, 1这五种面值的钱,问共有多少种不同的找法。 二、解析 看到这道题,第一反应是用DAG的记忆化搜索法求解,即每个金额V指向V-coins[i]。但这样会出现一个问题,就是重复计数的问题。比如16块钱,10->5->1的找法和1->...
2020-09-02
0
858
Uva 437 动态规划 之 DAG的最长路问题
来自专栏
一、题意 有n(n<=30)种立方体,每种有无穷个。现在要求你选一些立方体摞成尽量高的一个柱子,上面的立方体底面长宽必须严格小于下面的立方体。问最大高度。 二、解析 由于上面的立方体底面长宽必须严格小于下面的立方体,因此不会出现环,也就是说这是一个典型的DAG(有向无环图)问题。 有向无环图可...
2020-09-02
0
486
Uva 1623 这道神龙喝水题真的太难了....
来自专栏
一、题意 某个城市有n个湖,每个湖初始装满水。在接下来的m天,每天要么不下雨,要么会恰好往一个湖里下暴雨。若下暴雨时,该湖已经装满水,则会发生水灾。你是一条神龙,你可以在不下雨的日子里喝光一个湖的水(也可以不喝)。给出接下来m天是否下雨以及会往哪些湖下暴雨,为了不引起水灾,你应该在不下雨的那几天里如...
2020-09-01
0
573
Uva 11536 一道双指针简单题
来自专栏
一、题意 输入n、m、k,你可以根据m得到一个长度为n的序列a[maxn](即a[maxn]已知)。现在要你在a[maxn]中找到一个包含 1~k 这k个整数的最短连续子序列。输出符合要求的最短连续子序列的长度。无解时输出无解。 二、解析 看到连续子序列,马上就觉得可以用滑动窗口或者说双指针的方法来...
2020-09-01
0
476
Uva 11235 进来学习学习RMQ算法
来自专栏
一、题意 输入n、q(n、q<=100000),然后输入一个长度为n的递增序列A(有重复元素)。之后是q次询问,每次询问输入两个数l、r,你需要输出在区间 A[l...r] 中出现次数最多的元素的出现次数。 二、解析 为了不超时,每次询问我们需要在O(1)~O(lgn)时间内作出回答。这就让我...
2020-09-01
0
480
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页