【题目描述】

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为$m$，尾标记为$r$，后一颗能量珠的头标记为$r$，尾标记为$n$，则聚合后释放的能量为$m * r* n$（Mars单位），新产生的珠子的头标记为$m$，尾标记为$n$。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

【题目链接】

CodeVS 1154 能量项链 【NOIP 2006】

【题目描述】

我们用以下规则定义一个合法的括号序列：

（1）空序列是合法的 （2）假如S是一个合法的序列，则 (S) 和[S]都是合法的 （3）假如A 和 B 都是合法的，那么AB和BA也是合法的

例如以下是合法的括号序列：

(), [], (()), ([]), ()[], ()[()]

以下是不合法括号序列：

(, [, ], )(, ([]), ([()

现在给定一些由'(', ')', '[', ，']'构成的序列 ，请添加尽量少的括号，得到一个合法的括号序列。

【题目链接】

CodeVS 3657 括号序列

【题目描述】

有n堆石子排成一列，每堆石子有一个重量$w_i$, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和$w_i + w_{i + 1}$。 问安排怎样的合并顺序，能够使得总合并代价达到最小。

【题目链接】

CodeVS 1048 石子归并 【NOIP 2000】

【快捷版题意】

有n扇门，每扇门后面有一个运算符号xor,or,and，和一个参数t。 一开始可以选择一个不超过m的非负整数，使得经过这n扇门经过运算后数字最大。 $n \leq 100000$， $0 \leq m,t \leq 10^9$

【题目描述】

下面进入OI题目传统，讲故事时间 ->

背包问题是一类经典问题，其本质是0/1线性规划，私以为背包问题的精髓在经典文章《背包九讲》中已基本道尽，本文结合自己有限的理解，总结了一下对最基本的几类背包问题的学习，并整理了相关的代码实现。

【题目链接】

BZOJ 3173 最长上升子序列 [TJOI2013]

【题目描述】

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

【题目链接】

HDU 5125 Magic balls [BestCoder Round#20]

【题目描述】

原文是英文就不搬了，快捷版题意：

有$n$个数，每个数有两个属性$a_i$，$b_i$，每次操作可以交换一个数的两个属性，即选取一个$i$然后$swap(a_i, b_i)$，可以进行$k$次操作，问操作后$a_i$形成的最长上升子序列长度。

最长上升子序列的$O(nlogn)$做法。

【问题描述】

给定$n$个数 $a_1 , a_2 , ... , a_n$

定义 $$f(i,j) = \sum_{k = i}^{j} a_k$$

求 $f(i,j)$ 的最大值

【题目描述】

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形： 设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。