解环题目与解题报告

1、解环拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。 “将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特萨大叫道。“拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄出任何声音，否则，我将按有关法律制罪。”为了帮助拜特萨！

2、链子上的环按整数1,2,n进行了编号。我们可以按照以下规则解开环：只有一个环时可以被连接到栅栏或从栅栏上拆开。 第1号环总能进行连接或拆开 如果1,.,k-1 (1=kn)环都被拆开，第k个环被连接时, 此时我们能连接或拆开 第k+1个环. 写一个程序：文本文件LAN.IN描述了拜特链的构成, 计算拆除拜特链上全部环的最少操作次数, 将结果写入文本文件LAN.OUT. 输入在文本文件LAN.IN 中的第1行有一个整数n, 1=n=1000.在第2行有n个用一个空格分隔的整数 o1,o2,.,on (每个都是0或1)，如果 oi=1, 那么第I个环和栅栏相连，如果 oi=0, 那么第I环没有和栅

3、栏相连。 输出文本文件 LAN.OUT中只包含一个整数，为解开拜特链的全部环的最少操作次数。输入示例41 0 1 0输出示例6解题报告初步分析为了看清问题的本质，我们将题目重述：任意给定一个01串S，以及下面两种操作：操作a：将S的第一个字符取反。操作b：若S1 . i 1 = 00000，Si = 1，那么将Si + 1取反。（1 = i = n 1）同时给出一个固定的目标串T = 000000。现在需要将初始串S反复执行上述两种操作，变换到目标串T。问：至少需要执行多少次操作？譬如S = 1010。执行操作b：1110执行操作a：0110执行操作b：0100执行操作a：1100执行操作b：

4、1000执行操作a：0000共进行了6次操作。稍加分析可知：性质1 同一种操作不能连续两次执行。证明 若连续执行同一操作两次，相当于没执行任何操作。所以不能将同一种操作连续两次执行。根据性质1，我们容易得到：性质2 将S变换到T的操作序列必然是：操作序列1：abab ba或者操作序列2：baba ba（最后执行的操作必然是a）那么一种最简单的算法构想就形成了：分别按照上述两种方法对S进行操作，得出所需得操作次数；取较小值作为答案。然而这种算法的效率十分低下。如果最后的结果是s，那么它的时间复杂度就是O(s)s最大可以达到2n！于是我不得不寻找新的方法广泛应用于计数、以高效而著称的动态规划就成了

5、我们首选的考察对象。动态规划模型要将S的每一位都变成0，显然最后一次执行的必须是操作a。故而我们可以将整个变换过程分解成：S 100000 00000即：将S的后n-1位全变为0。将S的第1位变为0。还是从实例入手：1 010 0101 110 1100 1100 100 1001 1001 000 0000 000图中左列是S = 1010变到T = 0000的过程。我们如果只关心它的后n-1位，如右列所示实际上是把S的后3位变换到“全零”的过程。这正吻合了我们前面的分析。然而后面n-1的变换又直接受到第一位取值的影响。当第一位为0时，后n-1位才能进行b操作；当第一位为1时，后n-1位才能

6、进行a操作。另一方面，对后n-1位进行变换同样要遵行性质2（操作a和b交替出现）。所以对后n-1位执行完一次操作a，就必须进行一次额外的操作，将原串的第一位取反；类似的，对后n-1位执行完一次操作b，也必须进行一次额外的操作，将原串中的第一位取反正如上图中方框匡起来的部分，后n-1位的每个状态都重复出现了两次，这是由于这个原因。设通过“操作序列1”将S的后i位全部变换到0所需的最少操作次数是fi, 1；通过“操作序列2”将S的后i位全部变换到0所需的最少操作次数是fi, 2。那么根据上文的分析可以列出状态转移方程：当第n - i + 1位是1时： fi, 1 = fi - 1, 2 * 2 + 1 fi, 2 = fi - 1, 1 * 2当第n - i + 1位是0时： fi, 1 = fi - 1, 1 * 2 + 1 fi, 2 = fi - 1, 2 * 2边界条件： f0, 1 = +，f0, 2 = 0求：minfn, 0, fn, 1。由于结果可能很大，所以要使用高精度运算。整个算法的时间复杂度是O(n)。（不包