【算法】DP-背包学习(视频+博客+练习题)-程序员宅基地

技术标签: 学习  算法  c语言  Powered by 金山文档  数据结构  

dp视频

背包视频

背包九讲

练习题

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

738810274445265

在上面的样例中,从 7→3→8→7→57→3→8→7→5 的路径产生了最大

输入格式

第一个行一个正整数 �r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入 #1复制

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出 #1复制

30

说明/提示

【数据范围】

对于 100%100% 的数据,1≤�≤10001≤r≤1000,所有输入在 [0,100][0,100] 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

题解

P1434 [SHOI2002] 滑雪

P1434 [SHOI2002] 滑雪

题目描述

Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 24−17−16−124−17−16−1(从 2424 开始,在 11 结束)。当然 2525-2424-2323-……-33-22-11 更长。事实上,这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 �R 和列数 �C。下面是 �R 行,每行有 �C 个数,代表高度(两个数字之间用 11 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

输入输出样例

输入 #1复制

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

输出 #1复制

25

说明/提示

对于 100%100% 的数据,1≤�,�≤1001≤R,C≤100。

题解

3. P1048 [NOIP2005 普及组] 采药

P1048 [NOIP2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗?

输入格式

第一行有 22 个整数 �T(1≤�≤10001≤T≤1000)和 �M(1≤�≤1001≤M≤100),用一个空格隔开,�T 代表总共能够用来采药的时间,�M 代表山洞里的草药的数目。

接下来的 �M 行每行包括两个在 11 到 100100 之间(包括 11 和 100100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入 #1复制

70 3

71 100

69 1

1 2

输出 #1复制

3

说明/提示

【数据范围】

  • 对于 30%30% 的数据,�≤10M≤10;

  • 对于全部的数据,�≤100M≤100。

【题目来源】

NOIP 2005 普及组第三题

题解

P4017 最大食物链计数

P4017 最大食物链计数

题目背景

你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。

题目描述

给你一个食物网,你要求出这个食物网中最大食物链的数量。

(这里的“最大食物链”,指的是生物学意义上的食物链,即最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者。)

Delia 非常急,所以你只有 11 秒的时间。

由于这个结果可能过大,你只需要输出总数模上 8011200280112002 的结果。

输入格式

第一行,两个正整数 �、�nm,表示生物种类 �n 和吃与被吃的关系数 �m

接下来 �m 行,每行两个正整数,表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数,为最大食物链数量模上 8011200280112002 的结果。

输入输出样例

输入 #1复制

5 7

1 2

1 3

2 3

3 5

2 5

4 5

3 4

输出 #1复制

5

说明/提示

各测试点满足以下约定:

【补充说明】

数据中不会出现环,满足生物学的要求。

题解

P1020 [NOIP1999 普及组] 导弹拦截

P1020 [NOIP1999 普及组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度,计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行,若干个整数,中间由空格隔开。

输出格式

两行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入 #1复制

389 207 155 300 299 170 158 65

输出 #1复制

6

2

说明/提示

对于前 50%50% 数据(NOIP 原题数据),满足导弹的个数不超过 104104 个。该部分数据总分共 100100 分。可使用�(�2)O(n2) 做法通过。

对于后 50%50% 的数据,满足导弹的个数不超过 105105 个。该部分数据总分也为 100100 分。请使用 �(�log⁡�)O(nlogn) 做法通过。

对于全部数据,满足导弹的高度为正整数,且不超过 5×1045×104。

此外本题开启 spj,每点两问,按问给分。


upd 2022.8.24upd 2022.8.24:新增加一组 Hack 数据。

题解

P1880 [NOI1995] 石子合并

P1880 [NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放 �N 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 22 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出一个算法,计算出将 �N 堆石子合并成 11 堆的最小得分和最大得分。

输入格式

数据的第 11 行是正整数 �N,表示有 �N 堆石子。

第 22 行有 �N 个整数,第 �i 个整数 ��ai 表示第 �i 堆石子的个数。

输出格式

输出共 22 行,第 11 行为最小得分,第 22 行为最大得分。

输入输出样例

输入 #1复制

4

4 5 9 4

输出 #1复制

43

54

说明/提示

1≤�≤1001≤N≤100,0≤��≤200≤ai≤20。

题解

P1541 [NOIP2010 提高组] 乌龟棋

P1541 [NOIP2010 提高组] 乌龟棋

题目背景

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。

题目描述

乌龟棋的棋盘是一行�N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第�N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中�M张爬行卡片,分成4种不同的类型(�M张卡片中不一定包含所有44种类型的卡片,见样例),每种类型的卡片上分别标有1,2,3,41,2,3,4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

输入格式

每行中两个数之间用一个空格隔开。

第11行22个正整数�,�N,M,分别表示棋盘格子数和爬行卡片数。

第22行�N个非负整数,�1,�2,…,��a1,a2,…,aN,其中��ai表示棋盘第�i个格子上的分数。

第33行�M个整数,�1,�2,…,��b1,b2,…,bM,表示M张爬行卡片上的数字。

输入数据保证到达终点时刚好用光�M张爬行卡片。

输出格式

11个整数,表示小明最多能得到的分数。

输入输出样例

输入 #1复制

9 5

6 10 14 2 8 8 18 5 17

1 3 1 2 1

输出 #1复制

73

说明/提示

每个测试点1�1s

小明使用爬行卡片顺序为1,1,3,1,21,1,3,1,2,得到的分数为6+10+14+8+18+17=736+10+14+8+18+17=73。注意,由于起点是11,所以自动获得第11格的分数66。

对于30%30%的数据有1≤�≤30,1≤�≤121≤N≤30,1≤M≤12。

对于50%50%的数据有1≤�≤120,1≤�≤501≤N≤120,1≤M≤50,且44种爬行卡片,每种卡片的张数不会超过2020。

对于100%100%的数据有1≤�≤350,1≤�≤1201≤N≤350,1≤M≤120,且44种爬行卡片,每种卡片的张数不会超过4040;0≤��≤100,1≤�≤�,1≤��≤4,1≤�≤�0≤ai≤100,1≤iN,1≤bi≤4,1≤iM

P1508 Likecloud-吃、吃、吃

P1508 Likecloud-吃、吃、吃

题目背景

问世间,青春期为何物?

答曰:“甲亢,甲亢,再甲亢;挨饿,挨饿,再挨饿!”

题目描述

正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个 �×�(�,�≤200)n×m(n,m≤200) 的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了 �×�n×m 个小方格,每一个方格中都有一个圆形的巨型大餐盘,上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的,因为吃了要拉肚子),他决定从自己所处的位置吃到餐桌的另一侧,但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。

由于李大水牛已饿得不想动脑了,而他又想获得最大的能量,因此,他将这个问题交给了你。

每组数据的出发点都是最后一行的中间位置的下方!

输入格式

第一行为m n(n为奇数),李大水牛一开始在最后一行的中间的下方

接下来为m*n的数字距阵.

共有m行,每行n个数字.数字间用空格隔开.代表该格子上的盘中的食物所能提供的能量.

数字全是整数.

输出格式

一个数,为你所找出的最大能量值.

输入输出样例

输入 #1复制

6 7

16 4 3 12 6 0 3

4 -5 6 7 0 0 2

6 0 -1 -2 3 6 8

5 3 4 0 0 -2 7

-1 7 4 0 7 -5 6

0 -1 3 4 12 4 2

输出 #1复制

41

说明/提示

快吃!快吃!快吃!

题解

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/heliotrope_jin/article/details/129472251

智能推荐

Oracle、MySQL、SQLserver、DB2等搬砖中常用函数整理~-程序员宅基地

文章浏览阅读324次。最近工作需要针对不同的客户经常切换使用不同的数据库,不同的数据库不同的函数把比较常用的一些函数整理一下,便于后续查找。

【ghost初级教程】 怎么搭建一个免费的ghost博客-程序员宅基地

文章浏览阅读259次。ghost博客系统无疑是这个月最火热的话题之一,这个号称”只为博客“的系统,早在项目开始之初就受到了众人的关注。它使用了当前最火热node.js技术,10月14日发布了V0.3.3版本。江湖传言它将是下一个wordpress。下面来看几张ghost博客的截图:看起来很酷,对吧!更重要的是搭建一个ghost博客非常非常的简单,ghost小组甚至在未来的几周之内会推出一项host服务,..._ghost博客如何关闭注册

《第一行代码Android》笔记十二:Android代码混淆ProGuard工作原理简介_keepclassmembers public class * extends android.vi-程序员宅基地

文章浏览阅读215次。ProGuard能够对Java类中的代码进行压缩(Shrink),优化(Optimize),混淆(Obfuscate),预检(Preveirfy) .1。压缩(Shrink):在压缩处理这一步中,用于检测和删除没有使用的类,字段,方法和属性   .2。优化(Optimize):在优化处理这一步中,对字节码进行优化,并且移除无用指令   .3。混淆(Obfuscate):在混..._keepclassmembers public class * extends android.view.view

C/C++STL常用容器用法总结_stl容器用法总结-程序员宅基地

文章浏览阅读3.3w次,点赞48次,收藏293次。一、容器概念:容器是储存其他对象的对象。被储存的对象必须是同一类型。基本特征:以下用X表示容器类型(后面会讲到),T表示储存的对象类型(如int);a和b表示为类型X的值;u表示为一个X容器的标识符(如果X表示vector<int>,则u是一个vector<int>对象。)表 达 式 返 回 类 型 说 明 复 杂 度 X::iterator 指向T的迭代器..._stl容器用法总结

laravel配置完database后不生效_laravel database文件加载无效-程序员宅基地

文章浏览阅读5.4k次。laravel配置完database后不生效1.配置database2.cmd下 cd 当前项目根目录3.刷新配置php artisan config:cache完成_laravel database文件加载无效

LINUX make menuconfig提示'make menuconfig' requires the ncurses libraries解决方法_linux make menuconfig requires the ncurses librayi-程序员宅基地

文章浏览阅读208次。很长时间没搞LinuxKernel的裁剪,最近要搞点东西,所以下了个最新的源码,想定制一个内核,在执行make menucofig的时候,居然提示如下:*** Unable to find the ncurses libraries or the*** required header files.*** ‘make menuconfig’ requires the ncurses libra..._linux make menuconfig requires the ncurses librayies

随便推点

Java----冒泡排序(BubbleSort)_冒泡排序csdnjavabubblesortpanle-程序员宅基地

文章浏览阅读413次。冒泡排序(BubbleSort)源代码:public class BubbleSort { public static void main(String[] args) { int[] arr = { 10, 7, 2, 9, 3, 5 }; int t; System.out.println("排序前的数组为:"); ..._冒泡排序csdnjavabubblesortpanle

oracle 常用写法--Union与Union All_oracle union和union all写法-程序员宅基地

文章浏览阅读2.1k次。Union:对两个结果集进行并集操作,不包括重复行,同时进行默认规则的排序; Union All:对两个结果集进行并集操作,包括重复行,不进行排序;_oracle union和union all写法

crontab计划任务统计内存使用情况_crontab占用内存-程序员宅基地

文章浏览阅读629次。编写crontab任务:每一分钟记录一次当前系统的内存使用情况,并附带时间。审题,题目要求1.查看系统内存使用情况2.把查看的内容记录下来3.附带时间4.编写crontab任务实验操作审题,题目要求1.查看系统内存使用情况top命令可以查看动态的内存使用情况2.把查看的内容记录下来可以用重定向符 >表示覆盖;>>表示追加。因为我们记录的并不只是一次,所以我们用>>3.附带时间实时时间,可以用date命令4.编写crontab任务crontab -e 命令直接编_crontab占用内存

spring mybatis 整合后mapper接口注入失败问题_mybatis mapper接口 为空-程序员宅基地

文章浏览阅读4.8w次,点赞4次,收藏7次。org.springframework.beans.factory.NoSuchBeanDefinitionException: No qualifying bean of type [com.fkhd.whiteshirt.daos.UserMapper] found for dependency: expected at least 1 bean which qualifies as auto_mybatis mapper接口 为空

VC2015运行库安装失败_vc2015运行库安装失败0x001113f8-程序员宅基地

文章浏览阅读4.1k次。VC2015安装失败,0x80240017-未指定的错误。32位操作系统64位操作系统_vc2015运行库安装失败0x001113f8

响应式布局过时了吗?_响应式网站淘汰-程序员宅基地

文章浏览阅读1.3k次,点赞2次,收藏3次。响应式布局Responsive design,意在实现不同屏幕分辨率的终端上浏览网页的不同展示方式。通过响应式设计能使网站在手机和平板电脑上有更好的浏览阅读体验。响应式布局不是趋势?我们看到大型电商,直播平台,问答类网站,都会开发一套PC端和一套独立的移动端,比如 某东桌面端 (某东移动端)[https://m.jd.com],还有一些小型网站….响应式设计仅是改善移动体验并没..._响应式网站淘汰

推荐文章

热门文章

相关标签