你所掌握的算法知识帮助你从Acme计算机公司获得了一份令人兴奋的工作，签约奖金为1万美元。你决定利用这笔钱进行投资，目标是10年后获取最大回报。你决定请Amalgamated投资公司管理你的投资，该公司投资回报规则如下：

Rinky Dink公司是一家制造溜冰场冰面修整设备的公司。这种设备每个月的需求量都在变化，因此公司希望设计一种策略来规划生产，需求是给定的，即它虽然是波动的，但是是可预测的。公司希望设计接下来的$n$个月的生产计划。

某种字符串处理语言能够允许程序员将一个字符串拆分成为两段。由于此操作需要复制字符串，因此需要$n$个时间单位来将一个$n$个字符串拆分为两段。假定一个程序员希望将一个20个字符的字符串在第2个，第8个，以及第10个字符串进行从左到右拆分。

假设你是一支棒球大联盟球队的总经理。在赛季休季期间，你需要签入一些自由球员。球队老板给你的预算为X美元，你可以使用少于X美元来签入球员，但如果超支，球队老板就会解雇你。

给定一幅彩色图像，它由$mtimes n$的像素$A[1cdots m,1cdots n]$构成，每个像素是一个红绿蓝$(RGB)$亮度的三元组。假定我们希望轻度压缩这幅图像。具体地，我们希望从每一行中删除一个像素，使得图像变窄一个像素。

我们可以通过在有向图$G=(V,E)$中使用动态规划的算法来实现语音识别功能。对每条边$(u,v) in E$打上一个声音标签$sigma (u,v)$，该声音来自于有限声音集$sum$ 。图中从特定的顶点$v_0 in V$开始的每条路径都对应模型产生一个可能的声音序列。对于一条有向路径，我们定义标签为路径中边的标签的简单连结。

公司内部结构关系是层次化的，即员工按主管–下属关系构成一棵树，根节点为公司主席。人事部按“宴会交际能力”给每个员工打分，分值为实数。Stewart教授是一家公司总裁的顾问，这家公司正在计划一个公司的聚会。这个公司有一个层次式的结构；也就是，管理关系形成一颗以总裁为根的树。人事部门按每个员工喜欢聚会的程度来...

使用等宽字符打印一段文本。输入文本为n个单词的序列，单词长度为$l_1,l_2, cdots l_n$个字符，将其打印在若干行上，每一行最多$Maxnum$个字符。如果某行包含第$i$到第$j(i leq j)$个单词，行尾额外空格符的数量是$M-j+i-sum_{k=i}^jl_k$，这个值必须是非负的。

最长回文子序列是正序与逆序相同的非空字符串。例如，所有长度为1的字符串，civic，racecar，aibobphobia都是回文。设计算法，求给定输入字符串的最长回文子序列。例如，给定输入character，算法应该返回carac。算法的运行时间是怎么样的？

给定一个有向无环图$G=(V,E)$，边权重为实数，给定图中的两个顶点$k,t$，设计动态规划算法，求从k到t的最长简单路径，子问题图是怎样的？算法的效率如何？

其他运算符 位逻辑运算符 我们能够通过位逻辑运算符从字中抽取位域。下面归纳两种常见的用法：如果某个函数达到了输入的末尾，可以用下面形式报告状态： <!--more--> {代码...} 如果某个函数到达了输入的末尾，则它可以报告如下内容： {代码...} |=能够在现有的状态上添加内容。 {代码...} 还有一种比较常见的使用...

Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express ...

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之...

其他运算符 位逻辑运算符 我们能够通过位逻辑运算符从字中抽取位域。下面归纳两种常见的用法：如果某个函数达到了输入的末尾，可以用下面形式报告状态： <!--more--> {代码...} 如果某个函数到达了输入的末尾，则它可以报告如下内容： {代码...} |=能够在现有的状态上添加内容。 {代码...} 还有一种比较常见的使用...

Josephus问题的定义如下：假设n个人排成环形，且有以正整数m<=n。从某个制定的人开始，沿环报数，每遇到第m个人就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1，2，...，n的(n, m)-Josephus排列。例如，(7,3)-Josephus排列为<3,6,2,7,5,1,4>。

第一部分：红黑树表示与旋转 红黑树是一种平衡二叉树，其性质不再赘述。红黑树的数据结构如下： {代码...} 值得特别说明的是，这里的T->nil表示的是哨兵结点，是为了方便之后的运算。 红黑树的旋转过程，如下图所示： 注意旋转的前后，从左到右，子树依次是y->left y->right x->right，但是y->right的par...

在广度优先算法中，有几个问题值得探讨。1、使用递归这个方法是欧拉回路问题中最广泛使用的一种方法。如果一个无向图是联通的，且最多只有两个奇点（就是度数为奇数的点），就一定存在欧拉回路。其中，两个奇点一定是一个为起点，另一个是终点，这样构成“从一个奇点出发，到另一个奇点回来”。起点的入度比出度大一，终点...