coder-River
coder-River
全部文章
题解
归纳(12)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
全部文章
/ 题解
(共82篇)
Hdu 4508 背包问题 之 复习一下完全背包问题
来自专栏
一、题意 输入包含多组测试用例。每组数据以一个整数n开始,表示每天的食物清单有n种食物。接下来n行,每行两个整数a和b,其中a表示这种食物可以带给湫湫的幸福值(数值越大,越幸福),b表示湫湫吃这种食物会吸收的卡路里量。最后是一个整数m,表示湫湫一天吸收的卡路里不能超过m。输出最大幸福值。 二、解析 ...
2020-09-03
0
622
Uva 624 背包问题 之 复习一下01背包问题
来自专栏
一、题意 给一个V(V<=10000)和一个n(n<=20),V代表磁带的最大长度,n表示n首曲子,然后给出每首曲子的长度,现在要求你选一些曲子放入磁带中,使得磁带的利用率最高,输出最终磁带中存放的曲子序列,并输出总长度。 二、解析 换了个皮也得认出这是一个01背包问题。翻译过来就是:往...
2020-09-03
0
716
Uva 116 动态规划 之 多阶段决策性问题 与 通过递归打印路径
来自专栏
一、题意 给一个n行m列的整数矩阵(n<=10, m<=100),从第一列的任何一个位置出发,每次可以往→、↗、↘走一格,最终到达最后一列。矩阵时环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行。现在要你找一条路线使得经过的数字之和最小。打印出路径和最小和。若有多解则输出字典...
2020-09-03
0
445
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
572
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
478
Uva 1617 有时候题目可能没有你想得那么复杂...
来自专栏
一、题意 给你n条线段(线段端点为整数,n<=100000),输入保证线段间没有包含关系,且保证有解。现在要求将每条线段截取长度为1的一小段,使得截取后的所有线段之间的空隙数目最少。输出空隙的最少数目。 二、解析 一开始用了一种比较复杂的方法:将所有线段按右端点排序后,每个线段尽量靠左边选取...
2020-09-01
0
445
Uva 1616 这道题要求输出分数解?我不管,先求个小数解出来
来自专栏
一、题意 输入n条线段,线段之间没有包含关系,要求你把每条线段截成原来的一条子线段,使得改变之后的所有线段长度相等且互不相交(端点可以重合)。求每条线段的最大长度,并用分数表示。 二、解析 刚看到要用分数表示时,我是很懵的,但后来仔细一想,其实这只是出题人的虚晃一枪,我们首先求出小数解,然后再转变为...
2020-09-01
0
502
首页
上一页
1
2
3
4
5
6
7
8
9
下一页
末页