全国青少年信息学奥林匹克联赛章节习题（四）.doc
动态规划 8.1 字串距离 源程序名 可执行文件名 输入文件名 输出文件名 blast.???（pas, c, cpp） blast.exe blast.in blast.out 【问题描述】 设有字符串 X，我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的 扩展串，如字符串 X 为”abcbcd”，则字符串“abcb□cd”， “□a□bcbcd□”和“abcb□cd □”都是 X 的扩展串，这里“□”代表空格字符。 如果 A1 是字符串 A 的扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度， 那么我扪定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符 的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已 知的定值 K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串中，必定存在 两个等长的扩展串 A1、B1，使得 A1 与 B1 之间的距离达到最小，我们将这一距离定义为 字符串 A、B 的距离。 请你写一个程序，求出字符串 A、B 的距离。 【输入】 输入文件第一行为字符串 A，第二行为字符串 B。A、B 均由小写字母组成且长度均不 超过 2000。第三行为一个整数 K（1≤K≤100），表示空格与其他字符的距离。 【输出】 输出文件仅一行包含一个整数，表示所求得字符串 A、B 的距离。 【样例】 blast.in blast.out cmc 10 snmn 2 【算法分析】 字符串 A 和 B 的扩展串最大长度是 A 和 B 的长度之和。如字符串 A 为“abcbd”，字 符串 B 为“bbcd”，它们的长度分别是 la=5、lb=4，则它们的扩展串长度最大值为 LA+LB=9， 即 A 的扩展串的 5 个字符分别对应 B 的扩展串中的 5 个空格，相应 B 的扩展串的 4 个字符 对应 A 的扩展串中的 4 个空格。例如下面是两个字符串的长度为 9 的扩展串： a□b c□b□d□ □b□□b□c□d 而 A 和 B 的最短扩展串长度为 la 与 lb 的较大者，下面是 A 和 B 的长度最短的扩展串： a b cbd b□bcd 因此，两个字符串的等长扩展串的数量是非常大的，寻找最佳“匹配”（对应位置字符 距离和最小）的任务十分繁重，用穷举法无法忍受，何况本题字符串长度达到 2000，巨大 的数据规模，势必启发我们必须寻求更有效的方法：动态规划。 记为 A 串中 A1 到 Ai 的一个扩展串，为 B 串中 B1 到 Bj 的一个扩展串。这两个扩展串形成最佳匹配的条件是（1）长度一样；（2）对应位置字符 距离之和最小。 首先分析扩展串与扩展串长度一样的构造方法。扩展串与扩展串可以从下列三种情况扩张成等长： （1）与为两个等长的扩展串，则在后 加一空格，加字符 Bj； （2）与为两个等长的扩展串，则在 添加字符 Ai，在后加一空格； （3）与为两个等长的扩展串，则在 后添加字符 Ai，在后添加字符 Bj。 其次，如何使扩展成等长的这两个扩展串为最佳匹配，即对应位置字符距离之和最小， 其前提是上述三种扩展方法中，被扩展的三对等长的扩展串都应该是最佳匹配，以这三种扩 展方法形成的等长扩展串(A1, A2, …, Ai>和也有三种不同情形，其中对应位 置字符距离之和最小的是最佳匹配。 为了能量化上述的构造过程，引入记号 g[i, j]为字符串 A 的子串 A1, A2, …, Ai 与字符串 B 的子串 B1, B2, …, Bj 的距离，也就是扩展串与扩展串是一 个最佳匹配。则有下列状态转移方程： g[i, j]=Min{g[i-1, j]+k, g[i, j-1]+k, g[i-1, j-1]+ ai bi } 0≤i≤La 0≤j≤Lb 其中，k 位字符与字符之间的距离； ai bi 为字符 ai 与字符 bi 的距离。 初始值：g[0, 0]=0 g[0, j]=j·k g[i, 0]=i·k 综上所述，本题的主要算法如下： （1）数据结构 var a, b:array[1..2000]of byte; {以 ASCII 码表示的字符串} g:array[0..2000, 0..2000]of longint; {各阶段的匹配距离} （2）读入字符串 A、B，转换为 ASCII 码 la:=0; lb:=0; while not(eoln(f)) do {子串长度单元} begin {从文件中读入一行字符} read(f, c); inc(la); a[la]:=ord(c); end; readln(f); while not(eoln(f)) do begin read(f, c); inc(lb); b[lb]:=ord(c); end; readln(f); （3）根据状态转移方程求 g[la, lb] g[0, 0]:=0; for i:=1 to la do g[i, 0]:=k+g[i-1, 0]; for j:=1 to lb do g[0, j]:=k+g[0, j-1]; for i:=1 to la do for j:=1 to lb do begin g[i, j]:=k+g[i-1,j]; temp:=g[i, j-1]+k; if g[i, j]>temp then g[i, j]:=temp; temp:=g[i-1,j-1]+abs(a[i]-b[j]); if g[i, j]>temp then g[i, j]:=temp; end; （4）输出 writeln(f, g[la, lb]); 8.2 血缘关系 源程序名 可执行文件名 输入文件名 输出文件名 family.???（pas, c, cpp） family.exe family.in family.out 【问题描述】 我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的 基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基 因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根 据家谱来估算两个妖怪之间相同基因的数量。 妖怪之间的基因继承关系相当简单：如果妖怪 C 是妖怪 A 和 B 的孩子，则 C 的任意一 个基因只能是继承 A 或 B 的基因，继承 A 或 B 的概率各占 50％。所有基因可认为是相互独 立的，每个基因的继承关系不受别的基因影响。 现在，我们来定义两个妖怪 X 和 Y 的基因相似程度。例如，有一个家族，这个家族中有 两个毫无关系(没有相同基因)的妖怪 A 和 B，及它们的孩子 C 和 D。那么 C 和 D 相似程度 是多少呢？因为 C 和 D 的基因都来自 A 和 B，从概率来说，各占 50％。所以，依概率计算 C 和 D 平均有 50％的相同基因，C 和 D 的基因相似程度为 50％。需要注意的是，如果 A 和 B 之间存在相同基因的话，C 和 D 的基因相似程度就不再是 50％了。 你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相 似程度。 【输入】 第一行两个整数 n 和 k。n（2≤n≤300）表示家族中成员数，它们分别用 1, 2, …, n 来表示。k（0≤k≤n-2）表示这个家族中有父母的妖怪数量（其他的妖怪没有父母，它们 之间可以认为毫无关系，即没有任何相同基因） 。 接下来的 k 行，每行三个整数 a, b, c，表示妖怪 a 是妖怪 b 的孩子。 然后是一行一个整数 m（1≤m≤n2） ，表示需要计算基因相似程度的妖怪对数。 接下来的 m 行，每行两个整数，表示需要计算基因相似程度的两个妖怪。 你可以认为这里给出的家谱总是合法的。具体来说就是，没有任何的妖怪会成为自己的 祖先，并且你也不必担心会存在性别错乱问题。 【输出】 共 m 行。可 k 行表示第 k 对妖怪之间的基因相似程度。你必须按百分比输出，有多少 精度就输出多少，但不允许出现多余的 0（注意，0.001 的情况应输出 0.1%，而不是.1%）。 具体格式参见样例。 【样例】 family.in family.out 74 0% 412 50% 523 81.25% 645 100% 756 4 12 26 75 33 【知识准备】 （1）基本的概率计算知识； （2）递推原理（包括记忆化搜索）。 【算法分析】 本题是一道概率计算题，但这个概率计算又是建立在 Family Tree 模型上的。Family Tree 是一个有向无环图，有明显的阶段性(辈分关系)，而且没有后效性（没有人可以成为 自己的祖先），符合动态规划模型的基本条件。因此，应该可以套用类似动态规划的方法来 解决。 我们先来明确一下相似程度的计算方法。 假设我们要求的是 A 和 B 的相似程度（设为 P(A, B)） ，那么有两种情况是显然的： （1）A=B:P(A, B)=1； （2）A 与 B 无相同基因：P(A, B)=0。 这是计算其他复杂情况的基础。因为动态规划就是从一些特定的状态（边界条件）出发， 分阶段推出其他状态的值的。 再来看一般的情况，设 A0 和 A1 是 A 的父母。那么，取概率平均情况，A 拥有 A0 和 A1 的基因各占一半。假设 A0 与 B 的相似程度为 P(A0, B)，A1 与 B 的相似程度为 P(A1, B)， 那么 P(A, B)与 P(A0, B)和 P(A1, B)之间应该是一个什么样的关系呢？很容易猜想到： P(A, B)=(P(A0, B)+P(A1, B))/2 但是，这只是一个猜想。要让它变为一个结论还需要证明： 我们用归纳法来证明。 首先，我们知道，在这个问题中不同基因都是从特定的祖先传下来的，不会出现同一个 基因采自不同的祖先的情况(注：这里的祖先是指那些没有父母的妖怪)。所以，如果 A 与 B 有相同的基因，这些基因必然来自同一个祖先。这里，我们最想说明的是，祖先那代是不存 在两个人，它们之间不同的基因相同的概率不一样，因为它们相同的概率都是 0。 现在，A 有祖先 A0 和 A1，A0 和 A1 与 B 的相似程度分别为 P(A0, B)和 P(A1, B)。从祖 先一代开始归纳，可由归纳假设 A0 与 B、A1 与 B 之间每个基因相同的概率都是一样的，分 别都是 P(A0, B)和 P(A1, B)。A 的单个基因，它可能是继承 A0 的，也可能是继承 A1 的， 概率各 50%。继承 A0 的话与 B 相同的概率是 P(A0, B)，继承 A1 的话与 B 相同的概率是 P(A1, B)。那么这个基因与 B 相同的概率就是： (P(A0, B)+P(A1, B))/2 因此，A 的每个基因与 B 相同的概率都是(P(A0, B)+P(A1, B))/2，具有相同的概率。进而， A 与 B 相同基因的数量概率平均也为(P(A0, B)+P(A1, B))/2，A 与 B 的相似程度 P(A, B)=(P(A0, B)+P(A1, B))/2 这样就归纳证明了 P(A, B)的概率递推公式。 下面总结一下前面得出的结论： (1)边界条件： ① A=B:P(A, B)＝1； ② A 与 B 无相同基因：P(A, B)=0； (2)递推关系： P(A, B)＝(P(A0, B)+P(A1, B))/2，其中 A0 和 A1 是 A 的父母 有了边界条件和递推关系，以及 Family Tree 的阶段性和无后效性作为前提，用动态规 划解决问题的所有条件都已满足。应该说，从理论上来讲，本题已经完全解决。下面需要讨 论的仅仅是实现方法而已。 动态规划的实现方法有两种：一种是逆向的递推，另一种是正向的记忆化搜索（递归）。 这两种方法都是可行的，区别仅仅在于，递推需要更多的考虑状态的阶段性，按照阶段计算 出所有状态的值；而记忆化搜索只需要承认状态具有阶段性，无需考虑阶段，只需要按照递 推式本身设计带记忆化的递归函数即可。 本题给出的仅仅是一棵 Family Tree，并没有给出 Family Tree 的阶段，如果要用递推 的话，就必须先给 Family Tree 分阶段（拓扑排序）。所以，本题显然更适合用记忆化搜索 来实现。 另外，需要注意的是，本题所求的答案是有多少精度就输出多少精度。300 个节点的图， 少说也可以构成几十层的 Family Tree，算出的结果至少也有小数点后几十位。所以，高精 度是必不可少的（保险起见，可以设置 300 位的高精度）。 分析一下本题的时间复杂度。动态规划的状态有 n2 个，转移代价为 O(C)（高精度计 算的代价） 。因此，时间复杂度为为 O(Cn2)，n≤300。 严格的讲，本题的算法不能算动态规划的方法，因为本题不存在最优化，应该仅仅是一 个递推。不过，从分析问题的过程来看，它里面包含了很多动态规划的思想，例如，阶段性 和无后效性，特别是使用了动态规划的一种实现方法记忆化搜索。 8.3 尼克的任务 源程序名 可执行文件名 输入文件名 输出文件名 lignja.???（pas, c, cpp） lignja.exe lignja.in lignja.out 【问题描述】 尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主 管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。 尼克的一个工作日为 N 分钟，从第一分钟开始到第 N 分钟结束。当尼克到达单位后他 就开始干活。如果在同一时刻有多个任务需要完戍，尼克可以任选其中的一个来做，而其余 的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去完成，假如某些任务 开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第 P 分钟开始， 持续时间为 T 分钟，则该任务将在第 P+T-1 分钟结束。 写一个程序计算尼克应该如何选取任务，才能获得最大的空暇时间。 【输入】 输入数据第一行含两个用空格隔开的整数 N 和 K(1≤N≤10000，1≤K≤10000)，N 表示尼克的工作时间，单位为分钟，K 表示任务总数。 接下来共有 K 行，每一行有两个用空格隔开的整数 P 和 T，表示该任务从第 P 分钟开 始，持续时间为 T 分钟，其中 1≤P≤N，1≤P+T-1≤N。 【输出】 输出文件仅一行，包含一个整数，表示尼克可能获得的最大空暇时间。 【样例】 lignja.in lignja.out 15 6 4 12 16 4 11 85 81 11 5 【算法分析】 题目给定的数据规模十分巨大：1≤K≤10000。采用穷举方法显然是不合适的。根据求 最大的空暇时间这一解题要求，先将 K 个任务放在一边，以分钟为阶段，设置 minute[i]表 示从第 i 分钟开始到最后一分钟所能获得的最大空暇时间，决定该值的因素主要是从第 i 分 钟起到第 n 分钟选取哪几个任务，与 i 分钟以前开始的任务无关。由后往前逐一递推求各阶 段的 minute 值： （1）初始值 minute[n+1]=0 （2）对于 minute[i]，在任务表中若找不到从第 i 分钟开始做的任务，则 minute[i]比 minute[i+1]多出一分钟的空暇时间；若任务表中有一个或多个从第 i 分钟开始的任务，这时， 如何选定其中的一个任务去做，使所获空暇时间最大，是求解的关键。下面我们举例说明。 设任务表中第 i 分钟开始的任务有下列 3 个： 任务 K1 P1=i T1=5 任务 K2 P2=i T2=8 任务 K3 P3=i T3=7 而已经获得的后面的 minute 值如下： minute[i+5]=4，minute[i+8]=5，minute[i+7]=3 若选任务 K1，则从第 i 分钟到第 i+1 分钟无空暇。这时从第 i 分钟开始能获得的空暇时 间与第 i+5 分钟开始获得的空暇时间相同。 因为从第 i 分钟到 i+5-1 分钟这时段中在做任务 K1， 无空暇。因此，minute[i]=minute[i+5]＝4。 同样，若做任务 K2，这时的 minute[i]=minute[i+8]=5 若做任务 K3，这时的 minute[i]=minute[1+7]=3 显然选任务 K2，所得的空暇时间最大。 因此，有下面的状态转移方程： [i 1] 1 （任务表中无以第i分钟开始的任务） Minute Minute [i ] Max{Minute [i t ]} （任务表中从第i分钟开始有1个或多个任务） Pj i j 其中，Tj 表示从第 i 分钟开始的任务所持续的时间。 下面是题目所给样例的 minute 值的求解。 任务编号 K 1 2 3 4 5 6 开始时间 P 1 1 4 8 8 11 持续时间 T 2 6 11 5 1 5 时刻 I 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 minute[i] 0 1 2 3 4 0 1 2 3 4 5 6 1 2 3 4 选任务号 k 0 0 0 0 0 6 0 0 4 0 0 0 3 0 0 2 注：选任务号为该时刻开始做的任务之一，0 表示无该时刻开始的任务。 问题所求得最后结果为从第 1 分钟开始到最后时刻所获最大的空暇时间 minute[1]。 主要算法描述如下： （1）数据结构 var p:array[1..10000]of integer; {任务开始时间} t:array[1..10000]of integer; {任务持续时间} minute:array[0..10001]of integer; {各阶段最大空暇时间} （2）数据读入 ① readln(n, k); {读入总的工作时间 n 及任务 k} ② 读入 k 个任务信息 for i:=1 to k do readln(p[i],t[i]); {假设任务的开始时间按有小到大排列} （3）递推求 minute[i] j:=k; {从最后一个任务选起} for i:=n downto 1 do begin minute[i]:=0; if p[i]<>i then minute[i]:=1+minute[i+1] {无任务可选} else while p[j]=i do {有从 i 分钟开始的任务} begin if minute[i+t[j]]>minute[i] then minute[i]:=minute[i+t[j]]; {求最大空暇 时间} j:=j-1; {下一个任务} end; end; （4）输出解 writeln(minute[1]); 8.4 书的复制 源程序名 可执行文件名 输入文件名 输出文件名 book.???（pas, c, cpp） book.exe book.in book.out 【问题描述】 现在要把 m 本有顺序的书分给 k 给人复制（抄写） ，每一个人的抄写速度都一样，一本 书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、 第三、第四本书给同一个人抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。 【输入】 第一行两个整数 m，k；（k≤m≤500） 第二行 m 个整数，第 i 个整数表示第 i 本书的页数。 【输出】 共 k 行，每行两个整数，第 i 行表示第 i 个人抄写的书的起始编号和终止编号。k 行的 起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。 【样例】 book.in book.out 93 15 123456789 67 89 【问题分析】 本题可以用动态规划解决，但是动态规划并不是一个聪明的方法，这个后面会提到。不 管怎样，我们还是先介绍动态规划的方法。 设 f(n, k)为前 n 本书交由 k 个人抄写，需要的最短时间，则状态转移方程为 n f(n, k)=min{max{f(i, k-1), Tj }, i=1, 2, …, n-1} j i 1 状态数为 n·k，转移代价为 O(n)，故时间复杂度为 O(n2·k)。 不难看出，上述方程满足四边形不等式，所以如果利用四边形不等式的性质，转移代价 由平摊分析可得平均为 O(1)。因此，时间复杂度可以降为 O(n·k)。 动态规划求出的仅仅是最优值，如果要输出具体方案，还需根据动态规划计算得到的最 优值，做一个贪心设计。具体来说，设最优值为 T，那么 k 个人，每个人抄写最多 T 页。按 顺序将书分配给 k 人去抄写，从第一个人开始，如果他还能写，就给他；否则第一个人工作 分配完毕，开始分配第二个人的工作；以后再是第三个、第四个、……直至第 k 个。一遍贪 心结束后，具体的分配方案也就出来了。贪心部分的复杂度是 O(n)的。 从前面的分析可以看到，动态规划部分仅仅是求出了一个最优值，具体方案是通过贪心 求得的。而动态规划这部分的时间复杂度却是相当之高，所以用动态规划来求最优值是很不 合算的。可以看到，当每人抄写的页数 T 单调增加时，需要的人数单调减少，这就符合了 二分法的基本要求。我们可以对 T 二分枚举，对每个枚举的 T，用贪心法既求出需要的人数 又求出具体的方案。所以，通过二分就能求得需要人数为 k 的最小的 Tmin 和相应的方案了。 时间复杂度为 O(nlog2c)，c 为所有书本的页数和。 从这道题目的解题过程中，我们可以看到动态规划也不是万金油，有时更一般的方法却 可以得到更好的结果。 8.5 多米诺骨 dom.???（pas, c, cpp） dom.exe dom.in dom.out 源程序名 可执行文件名 输入文件名 输出文件名 【问题描述】 多米诺骨牌有上下 2 个方块组成，每个方块中有 1~6 个点。现有排成行的 n 个多米诺 骨牌如图 8-1 所示。 ● ● ● ● ● ● ● ● ● ● ● ● ● 上方块中点数之和记为 例如在图 8-1 中， ● ● ● ● ● ● ● ，下方块中点数之和记为 ，它们的差为 1 2 1 =6+1+1+1=9， =1+5+3+2=11， 1 2 1 2 。 2 =2。每个多米诺 骨牌可以旋转 180°，使得上下两个方块互换位置。 编程用最少的旋转次数使多米诺骨牌上下 2 行点数之差达到最小。 对于图 8-1 中的例子，只要将最后一个多米诺骨牌旋转 180°，可使上下 2 行点数之 差为 0。 【输入】 输入文件的第一行是一个正整数 n(1≤n≤1000)，表示多米诺骨牌数。接下来的 n 行 表示 n 个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块 中的点数 a 和 b，且 1≤a，b≤6。 【输出】 输出文件仅一行，包含一个整数。表示求得的最小旋转次数。 【样例】 dom.in dom.out 4 1 61 15 13 12 【问题分析】 本问题可归约为经典的背包问题。 假设一个骨牌的点数差的绝对值是 s，那么它实际可以取到的点数差就是-s 或 s。我们 不妨对取值进行一下平移，让每个骨牌可以取到的点数差为 0 和 2s。这样，骨牌的“取正 值还是负值”就转化为背包的“取与不取”了。 那么，我们求解的目标会怎样变化呢？本来，我们的目标是让取值的总和为 0。现在， 我们对每个骨牌的取值作了平移，平移的距离为 s。那么，最后的取值总和就应该是∑s， 即所有骨牌的平移距离之和。 8.6 平板涂色 源程序名 可执行文件名 输入文件名 输出文件名 paint.???（pas, c, cpp） paint.exe paint.in paint.out 【问题描述】 CE 数码公司开发了一种名为自动涂色机（APM）的产品。它能用预定的颜色给一块由 不同尺寸且互不覆盖的矩形构成的平板涂色。 ──→x 0 1 2 3 4 5 6 │ 0 │ Red Blue ↓ (B) 1 y (A) Blue Red 2 (E) Blue (D) 3 (C) 4 Red Blue (G) 5 (F) 6 为了涂色，APM 需要使用一组刷子。每个刷子涂一种不同的颜色 C。APM 拿起一把有 颜色 C 的刷子，并给所有颜色为 C 且符合下面限制的矩形涂色： 为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它上方的矩形涂色后，才能涂 色。例如图中矩形 F 必须在 C 和 D 涂色后才能涂色。注意，每一个矩形必须立刻涂满，不 能只涂一部分。 写一个程序求一个使 APM 拿起刷子次数最少的涂色方案。注意，如果一把刷子被拿起 超过一次，则每一次都必须记入总数中。 【输入】 文件 paint.in 第一行为矩形的个数 N。下面有 N 行描述了 N 个矩形。每个矩形有 5 个 整数描述，左上角的 y 坐标和 x 坐标，右下角的 y 坐标和 x 坐标，以及预定颜色。 颜色号为 1 到 20 的整数。 平板的左上角坐标总是(0, 0)。 坐标的范围是 0..99。 N 小于 16。 【输出】 输出至文件 paint.out，文件中记录拿起刷子的最少次数。 【样例】 paint.in paint.out 7 3 00221 02162 20421 12442 14361 40641 34662 【问题分析】 指数型动态规划。 由于 N 小于 16，故可以以一个 N-bit 的二进制数 A 作为状态，其中每个二进制位表示 一个格子的涂色情况，二进制位 0 表示该格子未被涂色，二进制 1 表示该格子已被涂色。 用 F[A]表示要得到状态 A，最少需要改变多少次颜色。对于每个状态 A，通过枚举涂色 方案来推新的状态。 8.7 三角形牧场 源程序名 可执行文件名 输入文件名 输出文件名 pasture.???（pas, c, cpp） pasture.exe pasture.in pasture.out 【问题描述】 和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围 有漂亮白色栅栏的三角形牧场。她拥有 N(3≤N≤40)块木板，每块的长度 Li(1≤Li≤40)都 是整数，她想用所有的木板围成一个三角形使得牧场面积最大。 请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。 【输入】 第 1 行：一个整数 N 第 2..N+1 行：每行包含一个整数，即是木板长度。 【输出】 仅一个整数：最大牧场面积乘以 100 然后舍尾的结果。如果无法构建，输出-1。 【样例】 pasture.in pasture.out 5 692 1 1 3 3 4 【样例解释】 692=舍尾后的（100×三角形面积） ，此三角形为等边三角形，边长为 4。 【问题分析】 二维的背包问题。 将所有的木板当作背包，木板的长度作为背包的重量。与普通背包问题不同的是，这里 有两个背包。所以，我们要求的不是重量 w 是否能得到，而是一个重量二元组(w0, w1)是否 能得到。求解的方法与普通背包问题基本相同，只不过状态是二维的。 求得所有可以得到的二元组后，枚举所有的二元组。对于任意的(w0, w1)，w0, w1 ， w—w0—w1(w 表示所有背包的总重量)即是对应的三角形三边之长(可能是非法三角形)。 这些三角形中面积最大者就是我们所求的答案。 8.8 分组 源程序名 可执行文件名 输入文件名 输出文件名 teams.???（pas, c, cpp） teams.exe teams.in teams.out 【问题描述】 你的任务是把一些人分成两组，使得： ·每个人都被分到其中一组； ·每个组都至少有一个人； ·一组中的每个人都认识其他同组成员； ·两组的成员人数近两接近。 这个问题可能有多个解决方案，你只要输出任意一个即可，或者输出这样的分组法不存 在。 【输入】 为了简单起见，所有的人都用一个整数标记，每个人号码不同，从 1 到 N。 输入文件的第一行包括一个整数 N（2≤N≤100），N 就是需要分组的总人数；接下来 的 N 行对应了这 N 个人，按每个人号码的升序排列，每一行给出了一串号码 Aij（1≤Aij≤ N，Aij≠i） ，代表了第 i 个人所认识的人的号码，号码之间用空格隔开，并以一个“0”结束。 【输出】 如果分组方法不存在，就输出信息“No solution”（输出时无需加引号）至输出文件； 否则用两行输出分组方案；第一行先输出第一组的人数，然后给出第一组成员的号码，每个 号码前有一个空格，同理给出第二组的信息。每组的成员号码顺序和组别顺序并不重要。 【样例】 teams.in teams.out 5 3135 2350 224 14530 1250 1230 43210 【问题分析】 首先，确定这样的一组集合(Ai, Bi)，集合 Ai 中的人必须和集合 Bi 的人分在不同组。这 些集合可通过人与人之间认识与不认识的关系得到。 得到这些集合对后，问题就转化为一个背包问题了——即如何分配这些二元组，使得两 边人数差尽量小。这个背包问题可以通过“平移”的方法转化为普通的背包问题。
全国青少年信息学奥林匹克联赛章节习题（四）.doc
