在一个 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入。问最多可以在棋盘上放多少个其实。
「COGS 738」数字梯形 - 费用流
一个数字梯形,共有 n
行,第一行有 m
个数字,每一行都比上一行多一个数字。从第一行的每一个数字开始,每一次向左下方或左上方走,直到最后一行,有以下三种规则:
- 任意两条路径没有公共部分;
- 任意两条路径只能在点(数字)上有公共部分,不能在边(数字与数字之间)上有公共部分;
- 任意两条路径可以在点上或边上有公共部分。
求分别在这三种规则下的路径所经过数字总和的最大值。
「COGS 734」方格取数 - 二分图最大独立集
在一个有 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大。
「COGS 439」软件补丁 - 记忆化搜索 + 位运算
现在有一个软件,共有 n
个 BUG,开发人员开发了 m
个补丁,每个补丁有一个应用条件,要求某些 BUG 比如存在,某些 BUG 可以不存在,某些 BUG 存在或不存在都可以;每个补丁有一个影响,会使某些 BUG 消失,会使某些 BUG 产生;每个 BUG 有一个应用时间。问修复所有 BUG 需要的最短时间为多少。
「COGS 727」太空飞行计划 - 最大权闭合图
W 教授正在为国家航天中心计划一系列的太空飞行。可供选择的实验集合为 ,这些实验需要使用的全部仪器的集合为 。实验 需要用到的仪器是 。仪器 的费用为 。实验 的赞助商为该实验结果支付 。设计方案使收益最大。
「COGS 731」最长递增子序列 - 线性 DP + 网络流
给定正整数序列 X1 ~ Xn
。
- 计算其最长递增子序列的长度
s
。 - 计算从给定的序列中最多可取出多少个长度为
s
的递增子序列。 - 如果允许在取出的序列中多次使用
X1
和Xn
,则从给定序列中最多可取出多少个长度为s
的递增子序列。
「COGS 729」圆桌聚餐 - 网络流
假设有来自 m
个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri
。会议餐厅共有 n
张餐桌,每张餐桌可容纳 ci
个代表就餐。
为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法,给出满足要求的代表就餐方案。
「COGS 396」魔术球问题 - 贪心
假设有 n
根柱子,现要按下述规则在这n根柱子中依次放入编号为 1,2,3,4 ...... 的球。
- 每次只能在某根柱子的最上面放球;
- 在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在 n
根柱子上最多能放多少个球。
「COGS 728」最小路径覆盖问题 - 二分图匹配
给定有向图 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始,长度也是任意的,特别地,可以为 0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。
设计一个有效算法求一个有向无环图 G 的最小路径覆盖。