【题目描述】

学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。

在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3...。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

【题目链接】

CodeVS 1378 选课 【CTSC 1997】

【问题描述】

现有$N$种物品，第$i$件物品的价值为$w_i$，花费为$c_i$，该物品有$n_i$件。 给你一个容量为$V$的背包，设计方案使得获得的价值最大。

【题目描述】

在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。

然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。

FJ有N(1 <= N <= 100,000)只排成一排的奶牛。 每只奶牛的效率是不同的，奶牛i的效率为Ei (0 <= Ei <= 1,000,000,000)。

靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，那么，这些奶牛就会罢工去开派对)。

因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。

【题目链接】

CodeVS 4654 修剪草坪

【题目描述】

烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。

在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。 为了使情报准确的传递，在m个烽火台中至少要有一个发出信号。

现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递。

【题目链接】

Tyvj 1313 烽火传递 【NOIP2010】

【写在前面】

单调队列，可以以优秀的时间复杂度解决队列中的最值问题，常用来优化一类单调的DP问题，是一些更加高级的优化方法（如斜率优化）的基础。

【题目描述】

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：

(1) 删除一个字符；

(2) 插入一个字符；

(3) 将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试编写程序，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。

【题目链接】

CodeVS 2598 编辑距离问题

【题目描述】

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。

例如，对于下面这圈数字（n=4，m=2）：

                                  2

                   4                           -1

                                 3

当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

【题目链接】

CodeVS 1058 数字游戏 【NOIP 2003】

【题目描述】

铁路线上有n（2 ≤ n ≤ 10000）个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下所示：

当 $0 < x ≤ L_1 ,\ price = C_1$ 当 $L_1 < x ≤ L_2,\ price = C_2$ 当 $L_2 < x ≤ L_3,\ price = C_3$

其中 $L_1，L_2，L_3，C_1，C_2，C_3$ 都是已知的正整数， 且$1≤L_1 < L_2 < L_3 ≤ 10^9, 1 ≤ C_1 < C_2 < C_3 ≤ 10^9$。 显然若两站之间的距离大于L3，那么从一站到另一站至少要买两张票。

注意：每一张票在使用时只能从一站开始到另一站结束。

对于给出的起点和终点，求出最省钱的方案。

【题目链接】

Tyvj 3317 火车票（清新版题面） CodeVS 1349 板猪的火车票 （恶搞版题面）

【题目描述】

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

1. 3 * 12=36
2. 31 * 2=62

这时，符合题目要求的结果是：31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

【题目链接】

CodeVS 1017 乘积最大 【NOIP 2000】

【题目描述】

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：

subtree的左子树的加分 × subtree的右子树的加分＋subtree的根的分数

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

【题目链接】

CodeVS 1090 加分二叉树 【NOIP 2003】