题目链接： [kuangbin带你飞]专题十二 基础DP1 E - Super Jumping! Jumping! Jumping! 题意 起点(-无穷)终点(+无穷)中间有n个点，各有一个值，现想从起点到达终点，只能前行不能后退，且下一步必须比前面的点的值大，求所有走的点的值总和最大是多少。 思路 dp[i] = max(dp[k] + a[j]); 1<=k<=i-1;最大递

题目链接： [kuangbin带你飞]专题十二 基础DP1 D - Doing Homework 题意 有n门功课需要完成，每一门功课都有时间期限以及你完成所需要的时间，如果完成的时间超出时间期限多少单位，就会被减多少学分，问以怎样的功课完成顺序，会使减掉的学分最少，有多个解时，输出功课名排列最小的一个。 思路 利用二进制位的方法来解题用过不少次，但真正意义上的状态压缩dp，这是第一道，有纪

题目链接： [kuangbin带你飞]专题十二 基础DP1 C - Monkey and Banana ** 题意 ** 给定箱子种类数量n，及对应长宽高，每个箱子数量无限，求其能叠起来的最大高度是多少(上面箱子的长宽严格小于下面箱子) ** 思路 ** 每种箱子有三种放置方式且数量无限，故可将每个箱子按三个箱子看待。对所有箱子按主长副宽进行先大后小排序，那么问题就成了求最大递增子串。因为n

题目链接： [kuangbin带你飞]专题十二 基础DP1 B - Ignatius and the Princess IV ** 题意 ** 给n(奇数)个数，定义特殊的数为在序列中出现次数不少于(n+1)/2次的数，找出这个特殊的数 ** 思路 ** 我ac的思路是直接排序，然后一次循环进行对出现次数最大值的判断。 还有一种方法是排序后找第n/2大的数，因为特殊数出现次数超过一

题目链接： [kuangbin带你飞]专题十二 基础DP1 A - Max Sum Plus Plus ** 题意 ** 给n个数，将其分为m部分，各部分之间不能有交叉重叠，求最大和 ** 思路 ** dp[i][j]表示前j个数分为i部分的最大和，则dp[i][j] = max(dp[i][j-1] + a[j], dp[i-1][k] + a[j]) i-1<=k<=j-1前

题目链接： kuangbin带你飞 专题四 最短路练习 P - The Shortest Path in Nya Graph ** 题意 ** 共n个点，n层(每个点单独一层)，相邻的两层之间权值为w还有m条额外的边，权值为v，求1到n的最短路 ** 思路 ** 本题可谓好题。时间空间都卡的相当死，硬把我从timeout逼到memorylimit。在求最短路上，本题没有什么难度，dijkst

题目链接： kuangbin带你飞 专题四 最短路练习 O - Extended Traffic ** 题意 ** 给定每条街的拥挤度p(x)，街a到街b的时间就是(p(b)-p(a))**3，求第一个点到第k个点的最短路，若无法到达或结果小于3，输出’?’。 ** 思路 ** 显然，题目可能存在负环，则所有负环上的点全应该输出’?’ ，因为它们必定小于3，所以，spfa判断负环，并进行标记

题目链接： kuangbin带你飞 专题四 最短路练习 N - Tram 题意 电动巴士在每个十字路口有一个默认方向，走向别的方向需要改动扳手。第一行给定十字路口的数量和起点终点剩余n行给定与第i个十字路口相通的方向，第一个为默认方向 思路 典型模版题。直接dijkstraps：读题好费时间，英语是硬伤 代码#include<iostream> #include<cstr

题目链接： kuangbin带你飞 专题四 最短路练习 L - Subway 题意 小明步行的速度是10km/h，地铁速度是40km/h，给定家和学校的坐标，再给定多条地铁线路站点的坐标，问小明从家到学校所需的最短时间 思路 典型的最短路，直接套用dijkstra就行，此题在读入数据上麻烦一点。还有一个重要问题，导致我茫然wrong了好几次。因为我是将每条地铁线路的站点读入后，便对这条线的站

题目链接： kuangbin带你飞 专题四 最短路练习 K - Candies 题意 给n个人分糖果，m组数据a，b，c；意思是a比b少的糖果个数绝对不超过c个，也就是d(b)-d(a) < c，求1比n少的糖果数的最大值。 思路 也是通过这个题第一次接触到差分约束这个东西，学习了下，很奇妙。令x-y<=z表示x最大比y大z。若b-a<=k1, c-b<=k2, c-

题目链接： kuangbin带你飞 专题四 最短路练习 J - Invitation Cards 题意 求源点到各点的往返最短路之和 思路 本体思路没什么难度，分别用正反图求两次单源最短路即可，邻接表不好逆置，直接在最初构建两个图即可。数据量相当大，timeout了两次，第一次是直接spfa，第二次用vector做邻接表仍然超时，第三次自己构建邻接表算是过了 代码#include<i

题目链接： kuangbin带你飞 专题四 最短路练习 I - Arbitrage 题意 给定多种货币之间的兑换关系，问是否可以套利 思路 可以判断正环是否存在，或者直接floyd后判断有没有v[i][i] > 1，有则说明可以套利因为数据量很小，所以直接floyd输入数据存在 a x a，即a和a之间的汇率(好坑啊，害我wrong那么多次) 代码#include<iostre

题目链接： kuangbin带你飞 专题四 最短路练习 H - Cow Contest 题意 n个牛进行比赛，现已知m个关系， 牛u可以胜过牛v。问最后可以确定排名位数的有几个牛 思路 Floyd获得两两牛之间的关系，如果一个牛可以胜过a个牛，b个牛可以胜过它，那么如果a＋b＝n－1，他的排名就可以确定 代码#include<iostream> #include<cstr

题目链接： kuangbin带你飞 专题四 最短路练习 G - MPI Maelstrom 题意 n个处理器，第一个处理器要广播消息到其他所有的处理器，求需要时间最短是多少（从第一个点出发，求到其他点最短路的最大值） 思路 没什么可说的，单源最短路，dijkstra。 代码#include<iostream> #include<cstring> #include&l

题目链接： kuangbin带你飞 专题四 最短路练习 F - Wormholes 题意 农场主拥有很多农场，在这些农场之间有很多条路，以及单向的虫洞，每条路走完会花费一定的时间，而冲动可以回到之前的时间，问农场主是否可以通过特定的路径看到出发前的自己？(也就是回到自己出发时间前的出发点) 思路 将农场看做点，路和虫洞看做边，那么显然虫洞是负权边，这样题目就转化为求给定图中是否有负环的问题了

题目链接： kuangbin带你飞 专题四 最短路练习 E - Currency Exchange 题意 有n种货币，你含有num面额的其中一种货币。给定m种交易明细，即货币a和b之间的手续费与兑换率。双向兑换时，手续费与兑换率不一定相同。求有没有可能，在多次兑换后你手中的货币大于num。 思路 以货币为点，交易情况为边，本题可转换为求最长路是否含正环的问题。用Bellman-Ford，但要

题目链接： kuangbin带你飞 专题四 最短路练习 D - Silver Cow Party 题意 n个农场，m条单向路，n个牛分别在n个农场，第x农场为终点，问每个牛从所在农场前往x农场的往返路程最小值是多少，求出n个牛中往返路程最小值最大是多少？ 思路 一看到这种求多个点最短路的问题，第一想到floyd，但1000^3，10亿，TimeLimit的可能性相当大，写完一交，果不然。重新

题目链接： kuangbin带你飞 专题四 最短路练习 C - Heavy Transportation 题意 有n个城市，n个城市之间有m条公路或桥梁，每个公路或桥都有一个最大载重量，问从城市1到城市n所能运送到货物到最大重量是多少 思路 显然1到n的最大承重量为所有公路的承重量的最小值那么本题就是要求1到n的所有可能路径中最大承重量最大的一条路，即所经过所有公路的载重量最小值 最大的一条

题目链接： [kuangbin带你飞]专题四 最短路练习 M - 昂贵的聘礼 题意 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。”探险

题目链接： [kuangbin带你飞]专题四 最短路练习 B - Frogger 题意 给定n个点，点1为起点，点2为终点，求点一到点二的所有路径中，求在所有路径中每条路径最大段的最小值 思路 用dijkstra，d[i]表示1到i的路径中最大路段的最小值 代码#include<iostream> #include<cstring> #include<cmat