信息学奥赛中的动态规划.pptx

主讲人 FireStorm 动态规划讲稿 数字三角形 IOI1994 题目描述Description如图所示的数字三角形 从顶部出发 在每一结点可以选择向左走或得向右走 一直走到底层 要求找出一条路径 使路径上的值最大 输入描述InputDescription第一行是数塔层数N 1 N 100 第二行起 按数塔图形 有一个或多个的整数 表示该层节点的值 共有N行 输出描述OutputDescription输出最大值 样例输入SampleInput51311812726614158127132411样例输出SampleOutput86 解法1 暴搜 DFS一遍遍历整个数字三角形 对于每个节点 我们有2个选择 那么 n层的数字三角形有2 n种可能 所以时间复杂度为O 2 n TLE 解法2 贪心 一路下去只找最大的可以吗 WA 解法3 最长路 将整个数字三角形看作一个由点和边组成的图 以a 1 1 为起点 求它到a n i 1 i n 的最长路Dijkstra算法 本题部分数据有负值 SPFA算法 O kM 的话应该能行Bellman Ford算法 O VE 有点危险啊Floyd算法 O n 3 你确定要用吗 方法可行但是打起来好麻烦 还有什么更好的算法吗 当然有 那就是本课要讲的内容 动态规划 分析这个数字三角形 我们可以发现 一个节点只会受到上面两个节点的值的影响 而上面节点的值也只会受到更加上面的节点的值的影响 由此可写出递归式dp i j max dp i 1 j dp i 1 j 1 a i j 上面这个递归式在动态规划中被叫做状态转移方程式 根据这个式子 我们可以从dp 1 1 开始递推 直到数字三角形的最后一行 时间复杂度O n 2 完全无压力 动态规划是优美的动态规划是神奇的动态规划是有趣的动态规划是简单的动态规划是卡骗分的动态规划是禁贪心的动态规划是防止爆0的动态规划最简单最好玩了我最喜欢动态规划了 什么鬼 0 1背包问题 MerkelandHellman1978 NOIP2005普及组 题目描述Description由于该题目的题目描述版本过多 不再描述输入描述InputDescription输入第一行有两个整数T 1 T 1000 和M 1 M 100 用一个空格隔开 T代表最大重量 M代表物品的数目 接下来的M行每行包括两个在1到100之间 包括1和100 的整数 分别表示采摘某个物品的时间和每个物品的价值 输出描述OutputDescription输出包括一行 这一行只包含一个整数 表示在不超过规定重量的情况下 可以拿到的最大价值 样例输入SampleInput1111样例输出SampleOutput1数据范围及提示DataSize Hint 数据规模 对于30 的数据 M 10 对于全部的数据 M 100 老规矩 暴搜TLE贪心一定WA最短路你可以试试 怎么办 动态规划才是王道 我们先分析下暴搜的过程 我们对每个物品进行了搜索 产生了大量的状态 每个状态包括三个要点 1 目前已用的背包的容量 这个不用多说2 目前已经获得的价值 这个也不用多说3 目前已经处理了多少物品 记录下已经处理物品数量的原因是由于每个物品只能拿一个 所以要记录下已经处理了多少物品 防止以后重复处理 有什么想法没 为什么不记录下相同的状态时的最优策略呢 在使用相同的容量和处理了相同的物品后 剩下的搜索过程应该是相同的 假如共有n个物品 我们已经处理了m个 那么还需要处理的物品数量就是n m 但是在背包剩余体积为v的情况下 剩下n m个物品产生的最优解应该是相同的 这样就可以简化搜索过程 但是前面的怎么办呢 前面的当然要最好的 于是 我们得到一条结论 在其他状态均相同的情况下 选择最好的总是对的 所以 我们可以开始优化这个搜索了 每次搜索到一个状态 就从之前搜到过的状态里找一遍 如果看见可以替换的状态就更新 众 你不觉得更慢了么 所以 怎么办呢 你还记的桶排序吗 直接用数组下标记录 时间复杂度O 1 这个可以这样做吗 没问题 看数据范围 1 T 1000 1 M 100 状态只需要记录下重量和已处理的物品数 空间复杂度O TM 128MB内存没问题至于状态转移方程式的话 dp i j max dp i 1 j dp i 1 j v i c i 我一般习惯写成 dp i 1 j max dp i j dp i 1 j dp i 1 j v i max dp i 1 j v i dp i j c i 这个看个人喜好就可以了 没有强制要求的处理时 只要for一遍 把数组填充好就可以啦 时间复杂度O TM P S 这字母是谁规定的 这么恶心 如果卡你空间怎么办 滚蛋动数组 你还记得斐波那契问题怎么做的吗 c a ba bb c根本不用开一个数组嘛 这个问题也一样 除了前一行 其他的状态根本就用不到嘛 那么 要你何用 也就是说 数组只留2行就可以了 每处理完一行 就把第二行的结果放回第一行 继续处理滚动数组是用时间换空间的一种策略 有没有更好的方法呢 背包问题可以用一维数组解决你造吗 由于重量没有负数 所以可以直接向后转移 而且不用向下转移了 但这样就有可能重复处理一个物品 怎么办 很简单 改变下方向 从后往前处理就可以啦 至此 01背包完满完成 难度增加的背包问题 更加喜 sang 闻 xin 乐 bing 见 kuang 的背包问题 超大背包问题 每个物品只能拿一次 物品数量M 100 背包容量T 10 9 每个物品的价值 100 每个物品的重量 10 9 由于本题物品的价值非常小 所以可以将dp数组改为由已处理的物品数量和价值 数组内存储内容改为当前所需的重量即可 二维背包问题 对于每个物品 分别有体积v和重量w 求体积和重量均不超标的情况下可以拿到的最大价值 维数改为三维 改变下转移 也可简化为二维 从后往前for得出正确答案 完全背包问题 每个物品可以拿无限次 只要不超过最大重量即可 思路1 背包 枚举 在状态转移时枚举每个物品可以拿的次数 时间复杂度O VNK 优化1 减少物品种类 对于一个物品来说 假如它的重量大于等于另一个物品且它的价值比另一个物品低 那么要它何用 可以直接省略掉该物品 所以只要先预对所有物品进行一遍O n 2 的预处理 就能带来很大的优化 优化2 转化为0 1背包 将一个物品看成多个物品 时间复杂度没有发生变化但是大家记得一个叫做鬼谷子的钱袋的题吗 如一个物品最多可以拿10个 则可以拆分成 1个该物品 2个该物品 3个该物品 4个该物品 达到log k 的级别 也是个不错的优化 思路2 用一维背包解决 大家还记得一维的背包解决方案吗 此题也可 只不过为了使一个物品可以重复计算 只需要将从后往前改为从前往后即可 时间复杂度O VN 多重背包问题 对于每个物品 可以拿不同的次数 如 有的1次 有的10次 有的100次 依然采取之前的二进制思想 简化问题 混合背包问题 对于一个背包问题 有多种物品可以选择 有只能拿一件的 有可以拿多个的 有可以无限拿的 这时候应该怎么办 这个问题综合了三种背包 代表这个问题可以使用各种背包问题的优化方法 优化1 采用完全背包问题的优化方式1 即可瞬间去除大量无用物品P S 简直就是个垃圾清理器 优化2 先不考虑多重背包 只考虑01背包和完全背包 那么 就可以用喜闻乐见的一维数组方法求解 只要在转移前判断下是从前往后还是从后往前转移就行了 那么多重背包怎么办 笨 用二进制转成多个01背包啊 金明的预算方案 NOIP2006提高组 题目描述Description金明今天很开心 家里购置的新房就要领钥匙了 新房里有一间金明自己专用的很宽敞的房间 更让他高兴的是 妈妈昨天对他说 你的房间需要购买哪些物品 怎么布置 你说了算 只要不超过N元钱就行 今天一早 金明就开始做预算了 他把想买的物品分为两类 主件与附件 附件是从属于某个主件的 右图就是一些主件与附件的例子 如果要买归类为附件的物品 必须先买该附件所属的主件 每个主件可以有0个 1个或2个附件 附件不再有从属于自己的附件 金明想买的东西很多 肯定会超过妈妈限定的N元 于是 他把每件物品规定了一个重要度 分为5等 用整数1 5表示 第5等最重要 他还从因特网上查到了每件物品的价格 都是10元的整数倍 他希望在不超过N元 可以等于N元 的前提下 使每件物品的价格与重要度的乘积的总和最大 设第j件物品的价格为v j 重要度为w j 共选中了k件物品 编号依次为j1 j2 jk 则所求的总和为 v j1 w j1 v j2 w j2 v jk w jk 其中 为乘号 请你帮助金明设计一个满足要求的购物单 输入描述InputDescription第1行 为两个正整数 用一个空格隔开 Nm 其中N 0 表示该物品为附件 q是所属主件的编号 输出描述OutputDescription只有一个正整数 为不超过总钱数的物品的价格与重要度乘积的总和的最大值 200000 样例输入SampleInput100058002040051300514003050020样例输出SampleOutput2200数据范围及提示DataSize Hint无 对于每个主件 它最多有2个附件 那么每个物品只有这几种情况 1 不带附件2 带附件A3 带附件B4 带附件A和B5 连主件都不拿那么只要在状态转移时枚举每个物品拿还是不拿 拿几个附件即可 不过好好看看还是能发现些什么的 这题放眼望去应该是个树形dp 好可怕的说 至此 背包问题全部完成 但这仅仅是简单的背包问题而已 区间型DP 别看我看标题 石子归并 经典区间型dp 题目描述Description有n堆石子排成一列 每堆石子有一个重量w i 每次合并可以合并相邻的两堆石子 一次合并的代价为两堆石子的重量和w i w i 1 问安排怎样的合并顺序 能够使得总合并代价达到最小 输入描述InputDescription第一行一个整数n n 100 第二行n个整数w1 w2 wn wi 100 输出描述OutputDescription一个整数表示最小合并代价样例输入SampleInput44114样例输出SampleOutput18数据范围及提示DataSize Hint无 分析下花费吧 花费是由两堆石子组成的 即 cost i j w i w i 1 w j 1 w j 要合并i j堆 必须要先合并i k堆和k 1 j堆 可以得出递推式js i j w i i jmin js i i js i 1 j js i j 1 js j j cost i j i j 然后怎么办 递归处理吗 我说你百分百超时你信吗 这节课学的啥 动态规划啊 开个数组 记录下来 直接转成递推 时间复杂度O n 2 完全无压力P S 这个题写代码还是稍微有点难度的 所以写不出来的童鞋可以考虑放 mei 弃 tian 本 yi 题 bian 能量项链 noip2006 题目描述Description在Mars星球上 每个Mars人都随身佩带着一串能量项链 在项链上有N颗能量珠 能量珠是一颗有头标记与尾标记的珠子 这些标记对应着某个正整数 并且 对于相邻的两颗珠子 前一颗珠子的尾标记一定等于后一颗珠子的头标记 因为只有这样 通过吸盘 吸盘是Mars人吸收能量的一种器官 的作用 这两颗珠子才能聚合成一颗珠子 同时释放出可以被吸盘吸收的能量 如果前一颗能量珠的头标记为m 尾标记为r 后一颗能量珠的头标记为r 尾标记为n 则聚合后释放的能量为m r n Mars单位 新产生的珠子的头标记为m 尾标记为n 需要时 Mars人就用吸盘夹住相邻的两颗珠子 通过聚合得到能量 直到项链上只剩下一颗珠子为止 显然 不同的聚合顺序得到的总能量是不同的 请你设计一个聚合顺序 使一串项链释放出的总能量最大 例如 设N 4 4颗珠子的头标记与尾标记依次为 2 3 3 5 5 10 10 2 我们用记号 表示两颗珠子的聚合操作 j k 表示第j k两颗珠子聚合后所释放的能量 则第4 1两颗珠子聚合后释放的能量为 4 1 10 2 3 60 暂时找不到能量项链这种高级玩意儿 拿这个代替下吧 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 4 1 2 3 10 2 3 10 3 5 10 5 10 710输出描述OutputDescription只有一行 是一个正整数E E 2 1 109 为一个最优聚合顺序所释放的总能量 样例输入SampleInput423510样例输出SampleOutput710数据范围及提示DataSize Hint无 众所皆知 丝带项链是环形的 也就是说 这个题相比起石子归并问题来说 变成了环形摆放 怎么办呢poi 用脑子想一想 可以想出 即使是一个环合并 也不会合并超过2圈也就是说 可以把这串项链看作2倍长 读入时就进行预处理 之后合并时只要找出在其中一点断开能得到的项链的最大能量值就可以了 乘积最大 NOIP2000 题目描述Description今年是国际数学联盟确定的 2000 世界数学年 又恰逢我国著名数学家华罗庚先生诞辰90周年 在华罗庚先生的家乡江苏金坛 组织了一场别开生面的数学智力竞赛的活动 你的一个好朋友XZ也有幸得以参加 活动中 主持人给所有参加活动的选手出了这样一道题目 设有一个长度为N的数字串 要求选手使用K个乘号将它分成K 1个部分 找出一种分法 使得这K 1个部分的乘积能够为最大 同时 为了帮助选手能够正确理解题意 主持人还举了如下的一个例子 有一个数字串 312 当N 3 K 1时会有以下两种分法 1 3 12 362 31 2 62这时 符合题目要求的结果是 31 2 62现在 请你帮助你的好朋友XZ设计一个程序 求得正确的答案 输入描述InputDescription程序的输入共有两行 第一行共有2个自然数N K 6 N 40 1 K 6 第二行是一个长度为N的数字串 输出描述OutputDescription结果显示在屏幕上 相对于输入 应输出所求得的最大乘积 一个自然数 样例输入SampleInput421231样例输出SampleOutput62数据范围及提示DataSize Hint本题由于比较老 数据实际也比较小 用longlong即可通过 这个题目要求用指定的乘号数量分开一个数 将它变得尽可能大 先找递推式 a i j k max a i i k 1 a i 1 j k 1 a i j 1 k 1 a j j k 1 a i j k 的含义为 从i到j段 使用了k个乘号所产生的最大乘积 还可以简化为a i k 含义为从1到i段使用了k个乘号所产生的最大乘积记录到dp数组里进行动态规划就好了 数的划分 NOIP2001 题目描述Description将整数n分成k份 且每份不能为空 任意两种划分方案不能相同 不考虑顺序 例如 n 7 k 3 下面三种划分方案被认为是相同的 115151511问有多少种不同的分法 输入描述InputDescription输入 n k 6 n 200 2 k 6 输出描述OutputDescription输出 一个整数 即不同的分法 样例输入SampleInput73样例输出SampleOutput4数据范围及提示DataSize 这个题目需要让人感到猎奇 不要想歪 的动态规划 对于一个数的划分方式 我们可以分为两种 1 划分的结果中有数字1的2 划分的结果中没有数字1的对于会产生数字1的划分结果 我们可以忽略掉那个1 那么 n划分成m部分有多少种方法等于n 1划分成m 1部分有多少种方法 对于不产生数字1的划分结果 我们有另一种巧 妙的办法 所有划分产生的数字统一减1 那么 n划分成m部分有多少种方法等于n m划分成m部分有多少种方法dp i j dp i 1 j 1 dp i j j 总的来说 区间型dp要比背包型dp难一些 所以下面来点简 单的dp 序列型dp 传说中最水的dp 最长上升子序列 题目描述Description给一个数组a1 a2 an 找到最长的上升降子序列ab1 ab2 abk 其中b1 b2 bk 输出长度即可 输入描述InputDescription第一行 一个整数N 第二行 N个整数 N 5000 输出描述OutputDescription输出K的极大值 即最长不下降子序列的长度 样例输入SampleInput593627样例输出SampleOutput3数据范围及提示DataSize Hint 样例解释 最长不下降子序列为3 6 7 这题还用讲么 RT 我的做法是开一个dp数组 记录下以该数字为开头且带有该数字的最长上升子序列的长度 应该没有和我一样的 合唱队形 NOIP2004 题目描述DescriptionN位同学站成一排 音乐老师要请其中的 N K 位同学出列 使得剩下的K位同学排成合唱队形 合唱队形是指这样的一种队形 设K位同学从左到右依次编号为1 2 K 他们的身高分别为T1 T2 TK 则他们的身高满足T1Ti 1 TK 1 i K 你的任务是 已知所有N位同学的身高 计算最少需要几位同学出列 可以使得剩下的同学排成合唱队形 输入描述InputDescription输入文件chorus in的第一行是一个整数N 2 N 100 表示同学的总数 第一行有n个整数 用空格分隔 第i个整数Ti 130 Ti 230 是第i位同学的身高 厘米 输出描述OutputDescription输出文件chorus out包括一行 这一行只包含一个整数 就是最少需要几位同学出列 样例输入SampleInput8186186150200160130197220样例输出SampleOutput4数据范围及提示DataSize Hint对于50 的数据 保证有n 20 对于全部的数据 保证有n 100 算法1 这道题要求百摆成合 唱队形 即前面一段单调递增 后面一段单调下降的序列于是就有了算法1 枚举队伍中的最高点 前后的队伍分别求最长上升子序列和最长下降子序列 时间复杂度O n 2 n 2 O n 3 虽然不超时 但是敲起代码来有点麻烦额 算法2 既然要枚举每一个点 不如直接求出以每个点为开头或结尾的最长上升和最长下降子序列 然后直接for一遍找出二者相加的最大值再减去1 因为队伍只有一个最高点 即可 代码简化了不少 而且时间复杂度压到了O n 2 大家都知道最长公共子序列和最长严格上升子序列吧 都是大水题吧 总有些不好的预感额 但是如果将两者结合起来呢 那就是LCIS LongestCommonIncreasingSubsequence 最长公共严格上升子序列 果然来了 题目描述Description熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目 小沐沐先让奶牛研究了最长上升子序列 再让他们研究了最长公共子序列 现在又让他们要研究最长公共上升子序列了 小沐沐说 对于两个串A B 如果它们都包含一段位置不一定连续的数字 且数字是严格递增的 那么称这一段数字是两个串的公共上升子串 而所有的公共上升子串中最长的就是最长公共上升子串了 奶牛半懂不懂 小沐沐要你来告诉奶牛什么是最长公共上升子串 不过 只要告诉奶牛它的长度就可以了 输入描述InputDescription第一行N 表示A B的长度 第二行 串A 第三行 串B 输出描述OutputDescription输出长度 样例输入SampleInput422132123样例输出SampleOutput2数据范围及提示DataSize Hint1 N 3000 A B中的数字不超过maxlongint 这题说实话我也不大会 不过我还得硬着头皮讲 好吧正题开始 dp i j 表示a串前i个数和b串前j个数且以b串第j个数结尾的最长公共严格上升子序列 好绕口 以后就叫LCIS了 LCIS的长度 然后根据最长公共子序列一题的状态转移方程式可以得出本题的状态转移方程式 dp i j dp i 1 j a i b j dp i j max dp i 1 k 1 a i b j a k b j 应该不是很难懂 填充dp数组不用我教了吧 恭喜各位完成序列型dp 棋盘型dp 最终boss前的最后一个dp 过河卒 A点有一个过河卒 需要走到目标B点 卒行走规则 可以向下 或者向右 同时在棋盘上的任一点有一个对方的马 如上图的C点 该马所在的点和所有跳跃一步可达的点称为对方马的控制点 例如上图C点上的马可以控制9个点 图中的P1 P2 P8和C 卒不能通过对方马的控制点 棋盘用坐标表示 A点 0 0 B点 n m n m为不超过20的整数 并由键盘输入 同样马的位置坐标是需要给出的 约定 C不等于A 同时C不等于B 现在要求你计算出卒从A点能够到达B点的路径的条数 1 n m 15 大水题一枚 水水就过了呗 卒走到一个格子的方式只有两种 1 从它左边的格子过来2 从它上面的格子过来那么 走到这个格子的方法数 走到上面格子的方法数 走到左边格子的方法数 骑士游历 题目描述Description设有一个n m的棋盘 2 n 50 2 m 50 如下图 在棋盘上有一个中国象棋马 规定 1 马只能走日字2 马只能向右跳问给定起点x1 y1和终点x2 y2 求出马从x1 y1出发到x2 y2的合法路径条数 输入描述InputDescription第一行2个整数n和m第二行4个整数x1 y1 x2 y2输出描述OutputDescription输出方案数样例输入SampleInput3030115315样例输出SampleOutput2数据范围及提示DataSize Hint2 n m 50 NOIP1997 和过河卒有什么区别额 不就是改改状态转移方程式啊这个还不会的话还要不要来Loi啊 传纸条 NOIP2008 题目描述Description小渊和小轩是好朋友也是同班同学 他们在一起总有谈不完的话题 一次素质拓展活动中 班上同学安排做成一个m行n列的矩阵 而小渊和小轩被安排在矩阵对角线的两端 因此 他们就无法直接交谈了 幸运的是 他们可以通过传纸条来进行交流 纸条要经由许多同学传到对方手里 小渊坐在矩阵的左上角 坐标 1 1 小轩坐在矩阵的右下角 坐标 m n 从小渊传到小轩的纸条只可以向下或者向右传递 从小轩传给小渊的纸条只可以向上或者向左传递 在活动进行中 小渊希望给小轩传递一张纸条 同时希望小轩给他回复 班里每个同学都可以帮他们传递 但只会帮他们一次 也就是说如果此人在小渊递给小轩纸条的时候帮忙 那么在小轩递给小渊的时候就不会再帮忙 反之亦然 还有一件事情需要注意 全班每个同学愿意帮忙的好感度有高有低 注意 小渊和小轩的好心程度没有定义 输入时用0表示 可以用一个0 100的自然数来表示 数越大表示越好心 小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条 即找到来回两条传递路径 使得这两条路径上同学的好心程度只和最大 现在 请你帮助小渊和小轩找到这样的两条路径 输入描述InputDescription输入的第一行有2个用空格隔开的整数m和n 表示班里有m行n列 1 m n 50 接下来的m行是一个m n的矩阵 矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度 每行的n个整数之间用空格隔开 输出描述OutputDescription输出共一行 包含一个整数 表示来回两条路上参与传递纸条的学生的好心程度之和的最大值 样例输入SampleInput33039285570样例输出SampleOutput34数据范围及提示DataSize Hint30 的数据满足 1 m n 10100 的数据满足 1 m n 50 大家有什么想法呢 首先 我们可以轻松的得到一个错误的算法 跑两遍数字三角形 很明显这个算法是错误的 因为有可能出现重复的路径 那么 这个算法就没用了吗 当然不是的 我们这个算法的想法是 先找出好心值最高的路径 然后归零 找好心值次高的路径 但是这样会导致出现重复路径 那么我们稍微改一下这个算法 让两人同时找好心值最高的路径那不就乱 套了了吗 所以 我们要改一下这个方法 让两人同时从左上角到右下角走 这样的话只要两人不走到同一个格子上 起点和终点除外 那么这条路径就是可行的 dp i j k l 分别记录纸条A和纸条B所在的位置 转移时考虑4种情况 1 A纸条向右 B纸条也向右2 A纸条向右 B纸条向下3 A纸条向下 B纸条也向下4 A纸条向下 B纸条向右 可是还能再优化不是吗 由于两张纸条移动的格子数是相同的 所以他们一定在同一条斜线上 所以dp数组优化到三维 i j k分别表示走过的格子数 纸条A所在的行 纸条B所在的行 这样 三维数组就可以表示出状态来 而且还减去了许多无用的状态 最終鬼畜道化師 M 树形dp 状压DP DP骗分 仅简单讲解 树形dp 顾名思义 在树上进行的DP郑州学习时应该有讲过 由于这一部分的题目我也不太会 所以每一部分只讲一题 没有上司的舞会 题目描述DescriptionUral大学有N个职员 编号为1 N 他们有从属关系 也就是说他们的关系就像一棵以校长为根的树 父结点就是子结点的直接上司 每个职员有一个快乐指数 现在有个周年庆宴会 要求与会职员的快乐指数最大 但是 没有职员愿和直接上司一起与会 输入描述InputDescription第一行一个整数N 1 N 6000 接下来N行 第i 1行表示i号职员的快乐指数Ri 128 Ri 127 接下来N 1行 每行输入一对整数L K 表示K是L的直接上司 最后一行输入0 0 输出描述OutputDescription输出最大的快乐指数 样例输入SampleInput7111111113236474453500样例输出SampleOutput5 嘛 这也是道很经典的树形dp题目了 这道题的评级是Diamond钻石 怎么看也不是noip提高难度的题 不过我还是得讲 对于一个职员来说 他只有两种状态 参加 不参加 有些人是不是想到状压那边去了 看本题数据范围啊 6000啊 那么 这题是不是就不可解了呢 当然可以解 不然为啥要出这道题 对于一个职员来说 他要么来 要么不来 如果他来 那么他的下属就一个都不敢来 这是废话 如果你的班主任天天去逛银座 那么你还敢去银座吗 于是 我们可以这样做 为啥到了关键时候就翻页 开数组dp 6000 2 dp i 0 代表i号职员不来时能得到的快乐值 dp i 1 则代表i号职员来时能得到的最大快乐值当这个人不来时 对他的下属是没有影响的 或者说 他的下属爱来来 不爱来不来 所以可得 dp i 0 max dp k 0 dp k 1 这里的k代表他的所有下属 因为他不来 他的下属来不来都行 而且对他的上司又没有影响 所以我们可以贪心的找最大的 dp i 1 dp k 0 a i k依然代表他的所有下属 如果他来了 那么他的下属就都不能来 所以就是他的下属全都不来的最大快乐值加上他的快乐值 这样就好做了 DFS一遍求出所有人的快乐值 可以证明 最后产生的图形一定是一棵树 所以 只要最后找出这个公司的超级大BOSS 并且找出他来和不来两个状态快乐值最大的那个 这个题就AC啦 P S 简直累人 状压dp TSP问题 旅行商问题 即TSP问题 TravellingSalesmanProblem 又译为旅行推销员问题 货郎担问题 是数学领域中著名问题之一 假设有一个旅行商人要拜访n个城市 他必须选择所要走的路径 路径的限制是每个城市只能拜访一次 而且最后要回到原来出发的城市 路径的选择目标是要求得的路径路程为所有路径之中的最小值 这个有点难懂额 没关系 codevs上就有这个题 题目描述Description有一个送外卖的 他手上有n份订单 他要把n份东西 分别送达n个不同的客户的手上 n个不同的客户分别在1 n个编号的城市中 送外卖的从0号城市出发 然后n个城市都要走一次 一个城市可以走多次 最后还要回到0点 他的单位 请问最短时间是多少 现在已知任意两个城市的直接通路的时间 输入描述InputDescription第一行一个正整数n 1 n 15 接下来是一个 n 1 n 1 的矩阵 矩阵中的数均为不超过10000的正整数 矩阵的i行j列表示第i 1号城市和j 1号城市之间直接通路的时间 当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同 也就是说道路都是单向的 输出描述OutputDescription一个正整数表示最少花费的时间 样例输入SampleInput30110101012101010102100样例输出SampleOutput8数据范围及提示DataSize Hint1 n 15 这个题有什么特点呢 这个题的特点是 N特别小 当然 N如果不