• 等级
  • 2615 访问
  • 59 原创
  • 1 转发
  • 101895 排名
  • 12 评论
  • 3 获赞

【2019.1.22】【DP】纪中C组T4——小明游天界

题目大意 有n个节点,有t条路径,点之间可以随意走,求从点1到点n(包括这俩点)路线长度刚好为m,经过的最多点数。(点可以重复走) Input 第一行,三个整数n,m,t,意义如题所述 接下来t行,每行三个整数x,y,z,表示景点x到景点y有一条道路,且从景点x到景点y或从景点y到景点x需要z个单位时间,两个景点之间可能会有多条道路。 Output 一行,一个整数,表示用刚好m个单位时间到达终点最...

2019-01-22 21:50:42

【2019.1.22】【背包】纪中C组T3——小明逛超市

题目大意 小明要去买东西,有m样物品。每样东西有它的价格和需要值。(重量和价值)小明的妈只给了他n元钱。。。他要买出最大的价值。 已知,物品分俩种,一种只有一个,一种有无限个。 Input 两个正整数n,m分别表示他所有的钱数和物品种类数。接下来m行每行三个正整数x,y,z表示单价为x的物品,他对该物品的需求度为y,z=0时表示该物品为无限量,z=1时表述该物品只有1件。 Output 一个正整数...

2019-01-22 21:31:39

最短路(Floyed-Warshall、Dijkstra、Bellman-Ford、SPFA)

文章目录DescriptionInputOutput4种做法勾股定理1.Floyed-Warshall算法O(N^3)Floyed-Warshall代码2.Dijkstra算法O(N^2)Dijkstra代码3.Bellman-Ford算法O(NE)Bellman-Ford代码4.SPFA算法O(kE) Description 平面上有n个点(N<=100),每个点的坐标均在-10000~1...

2019-01-18 20:14:08

【最短路Dijkstra】【图论】最小花费

Description 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。 Input 第一行输入两个用空格隔开的正整数n和m,分别表示总人数和可以互相转账的人的对数。以下m行每行输入三个用空格隔开的正整数x,y,z,表示标号为x的人和标号为y的人之间互相转账需要扣除...

2019-01-18 15:35:29

【图论】【最短路】牛的旅行

题目描述 农民 John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个牧区通过任何路径都不连通。这样,Farmer John就有多个牧场了。 John想在牧场里添加一条路径(注意,恰好一条)。对这条路径有以下限制: 一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场...

2019-01-17 11:18:08

【DFS】【BFS】【邻接表】【STL】求连通分量

-Description - 求一个图的连通分量 -Input- n 顶点数(<=100) 边 -Output- 连通分量(例子为4) 方法: (写了那么多,就当是摸鱼吧) DFS DFS+邻接表 BFS BFS+邻接表 DFS 很快就打完了 #include<cstdio> using namespace std; in

2019-01-05 09:22:34

【DP】花店橱窗布置

-Description 题目描述- 某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按1到V顺序编号,V是花瓶的数目。花束可以移动,并且每束花用1到F的整数标识。如果I < J,则花束I必须放在花束J左边的花瓶中。例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有花束在放入花瓶时必须保持其标识数的顺序...

2019-01-02 17:14:27

【DP】拔河比赛

-Description 题目- 一个学校举行拔河比赛,所有的人被分成了两组,每个人必须(且只能够)在其中的一组,要求两个组的人数相差不能超过1,且两个组内的所有人体重加起来尽可能地接近。 -Input- 输入数据的第1行是一个n,表示参加拔河比赛的总人数,n<=100,接下来的n行表示第1到第n个人的体重,每个人的体重都是整数(1<=weight<=450)。 -Output-...

2019-01-02 16:21:13

【记忆化搜索】【DP】滑雪

Description 题目描述 Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21...

2018-12-30 10:44:07

【DP】数字游戏

Description 题目描述 小W发明了一个游戏,他在黑板上写出了一行数字a1,a2,a3,……,an,然后给你M个回合的机会,每会回你可以从中选择一个数字擦去它,接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合,所有你擦去的数字之和就是你所得的分数。   小W和他的好朋友小Y玩了这个游戏,可是他发现,对于每个给出的a和b序列,小Y的得分总比他高,所以他就很不服气。于是他想让你帮他...

2018-12-29 21:54:31

【DP】大厅安排

Description 题目描述 有一个演讲大厅需要GEORGE管理,演讲者们事先定好了需要演讲的起始时间和中止时间。GEORGE想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定,目标自然是使演讲者使用大厅的时间最长。为方便起见,假设在某一时刻一个演讲结束,另一个演讲就可以立即开始。   计算演讲大厅最大可能的使用时间。 Input 第一行为一个整数n,n <= 100,表...

2018-12-29 21:26:57

【DP】石子合并

Description 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务:   对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。    Input 输入包括多组测试数据,每组测试数据包括两行。 第1 行是正整数n...

2018-12-27 17:29:39

取数字问题

题目 Description 给定M*N的矩阵,其中的每个元素都是-10到10之间的整数。你的任务是从左上角(1,1)走到右下角(M,N),每一步只能向右或向下,并且不能走出矩阵的范围。你所经过的方格里面的数字都必须被选取,请找出一条最合适的道路,使得在路上被选取的数字之和是尽可能小的正整数。 Input 第一行两个整数M,N,(2<=M,N<=10),分别表示矩阵的行和列的数目。 接...

2018-12-22 10:46:36

【DP】多米诺骨牌

Description 题目描述

2018-12-21 21:00:30

【DP】方格取数

良好的码风是进步开始。 (虽然怎么看现在的代码,都还是不够好看) Description 题目描述 设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例):  某人从图的左上角的A 点出发,可以向下行走,也可以向右走,直到到达右下角的B点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。   此人从A点到B 点共...

2018-12-20 17:39:53

【DP】分组背包

题目大意 背包容量为v。现有n个物品,它们都有自己的重量和价值。 物品分成t组,每组最多选一个物品。 求背包能装下的最大价值。 输入 第一行:三个整数,v(背包容量,v<=200),n(物品数量,n<=30)和t(最大组号,t<=10); 第2…n+1行:每行三个整数wi,ci,p,表示每个物品的重量、价值、所属组号。 输出 仅一行,一个数,表示最大总价值。 思路 DP 首先,循...

2018-12-19 16:57:21

【DP】书的复制

Description 题目描述 现在要把m本有顺序的书分给k个人复制(抄写),每个人的抄写速度都一样,一本书不允许分给两个或两个以上的人抄写,分给每个人的书,必须是连续的,比如不能把第一、第三、第四本书给同一个人抄写。 现在请你设计一种方案,使得复制时间最短。复制时间为抄写最多的人用去的时间。 Input 第一行两个整数,m,k(k<=m<=500) 第二行为m个整数,第i个数表示第...

2018-12-15 16:18:44

【DP】农田个数

Description 题目描述 你的老家在河北农村。过年时,你回老家去拜年。你家有一片NM农田,将其看成一个NM的方格矩阵,有些方格是一片水域。你的农村伯伯听说你是学计算机的,给你出了一道题: 他问你:这片农田总共包含了多少个不存在水域的正方形农田。   两个正方形农田不同必须至少包含下面的两个条件中的一条:   边长不相等   左上角的方格不是同一方格 Input 输入数据第一行为两个由空...

2018-12-15 15:25:00

【DP】能量项链

Description 题目描述 在MarsMars星球上,每个MarsMars人都随身佩带着一串能量项链。在项链上有NN颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是MarsMars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能...

2018-12-15 14:38:10

【DP】矩阵链相乘

-Description 题目描述- 假设我们要用标准的矩阵乘法来计算M1,M2,M3三个矩阵的成绩M1M2M3,这三个矩阵的维数分别是210,102,210,如果把M1,M2相乘,然后再与M3相乘,那么要乘2102+2210=80次,如果代之以用M2,M3相乘的结果去乘M1,那么乘法的次数变成了10210+210*10=400,执行M1(M2M3)耗费的时间是执行乘法(M1M2)M3的5倍。 -...

2018-12-14 21:58:20

SSL_HKY

关注
  • 中国 广东省 东莞市
奖章
  • 持之以恒