5

输出解析：

这是那些符合题意的等差三元组： 1 2 3 2 3 4 2 4 6 3 6 9 4 6 8

Volume（快速排序+统计技巧）

直线上有N个点，每个点的坐标都是整数，1<=N<=10000。求每对点之间的距离总和的两倍。坐标范围是0到1000000000。

输入：volume.in

第一行是N。

接下来的N行，每行一个整数，表示每个点的坐标。

输入：volume.out

一个整数，表示每对点之间的距离总和的两倍。

样例： 输入 5 1 5 3 2 4 输出 40

巨大的牛棚bigbrn (动态规划)

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，

想找一个能够让他在空旷无树的地方修建牛棚的地方。假定他的农场划分成 N x N 的方格。

输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。

牛棚的边必须和水平轴或者垂直轴平行。

考虑下面的方格，它表示农夫约翰的农场，'.'表示没有树的方格，'#'表示

有树的方格

1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . # . . . . . 7 . . . . . . . . 8 . . . . . . . .

最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。

输入格式：(bigbrn.in)

第1行: 两个整数： N （1 <= N <= 1000），农场的大小，和 T （1 <= T <= 10000）有树的方格的数量。

第2到T+1行: 两个整数（1 <= 整数 <= N)，有树格子的横纵坐标。

输出格式：(bigbrn.out)

输出文件只由一行组成，约翰的牛棚的最大边长。 样例 输入： 8 3 2 2 2 6 6 3

输出： 5

比武大会（动态规划或贪心）

参赛者围成一个圆圈，每个人可以和跟他相邻的人比武，胜利者留在原地，失败者淘汰出局。大会的组织者已经知道每位选手的能力值，能力值大的一定可以战胜能力值小的（能力值相同时，不会有平局，必有一方被淘汰）。同时为了比赛更加激烈，他们倾向于让能力值接近的选手比武。所以他们想安排一个比武的顺序，在不改变参赛者现在位置的条件下，使得所有比赛中两名选手能力值差别的总和最小。

输入：fight.in

第1行1个整数n，表示参赛的人数（2<=n<=200）。

第2行n个数，以此表示圆上第1，2，??，n个人的能力值（为不超过

10000的非负数）。显然，第n个人和第1个人相邻。

输出：fight.out

一个整数，为n-1场比赛双方能力值差的绝对值之和的最小值。

样例 fight.in fight.out 3 2 2 3 1 蜘蛛网（递推）

蜘蛛拉出n条直线构成无限大的蜘蛛网，这n条直线没有三线共点的情况。这样的蜘蛛网能有多少种不同的交点数？

例如4条直线的蜘蛛网，可以有0、3、4、5、6共5种不同的交点数情况，这些交点数情况之和为0＋3＋4＋5＋6＝18。 输入：web.in

一个数n，1<=n<=100。 输出：web.out

输出两个数，分别表示有多少种不同的交点数和所有情况中交点数之和，中间用一个空格隔开。 样例 输入： 4 输出： 5 18

矩形合并enclose（迭代法）

有n个矩形的区域，边都平行于坐标轴。如果两个矩形内部的公共部分面积大于零，就要合并，合并后仍旧是一个矩形，边都平行于坐标轴，而且是包含着两个矩形的面积最小的矩形。如下图所示：

******** ************* * * * * * * * * * ++++++++++ -> * * * + * + * * ***+**** + * * + + * * ++++++++++ *************

当然，新的矩形也有可能再和其他矩形合并。求最终有几个矩形和矩形的总面积。

输入：(enclose.in)

第一行是n，1<=n<=100。 接下来的n行，每行描述一个矩形。共4个整数，分别表示左下角和右上角的顶点坐标。坐标分量范围在0到10000之间。

输出：(enclose.out)

两个整数，用一个空格分开。分别表示最后合并完的矩形数和矩形的总面积。

样例： 输入 3

0 0 5 2 8 8 9 9 2 1 6 4 输出 2 25

解释：两个矩形为(0, 0)-(6, 4)和(8, 8)-(9, 9)，总面积是6*4+1*1=25。

机器人robots（贪心）

地图标有若干个G，表示垃圾。有一些捡垃圾的机器人，可以从左上角(1, 1)走到右下角，沿途捡起地上的垃圾。但机器人只能往右或往下走。求最少需要几个机器人。下面是一个地图：

以下有两种方案，最少要2个机器人。