题目2 : 建造金字塔
时间限制:4000ms 单点时限:2000ms 内存限制:256MB 描述 在二次元中，金字塔是一个底边在x轴上的等腰直角三角形。
你是二次元世界的一个建筑承包商。现在有N个建造订单，每个订单有一个收益w，即建造此金字塔可获得w的收益。对每个订单可以选择建造或不建造。
建造一个金字塔的成本是金字塔的面积，如果两个或多个金字塔有重叠面积，则建造这些金字塔时重叠部份仅需建造一次。
建造一组金字塔的总利润是收益总和扣除成本。现给出这些订单，请求出最大利润。
输入 输入数据第一行为一个整数T，表示数据组数。
每组数据第一行为一个整数N，表示订单数目。
接下来N行，每行三个整数x, y, w，表示一个订单。(x, y)表示建造出的金字塔的顶点，w表示收益。
输出 对于每组数据输出一行”Case #X: Y”，X表示数据编号（从1开始），，Y表示最大利润，四舍五入到小数点后两位。
数据范围 1 ≤ T ≤ 20
0 ≤ w ≤ 107
小数据
1 ≤ N ≤ 20
0 ≤ x, y ≤ 20
大数据
1 ≤ N ≤ 1000
0 ≤ x, y ≤ 1000
样例输入 3 2 2 2 3 6 2 5 3 1 1 1 2 2 3 3 3 5 3 1 1 1 2 2 3 3 3 6 样例输出 Case #1: 1.00 Case #2: 0.00 Case #3: 1.00
dp。
顶点为这一段区间。
首先把金字塔按照左端点排序（），这一步非常关键！！
设表示前的最大获利。
然后分三种情况转移，即第大小关系: ① ② ③
还有一个转移是只放第个这一种。
在前两种情况中，我们可以保证第），因为是按照左端点排序的！！！于是重叠面积就很好算了。
题目3 : 质数相关
时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 两个数a和 b 被称为质数相关，是指a × p = b，这里p是一个质数。一个集合S被称为质数相关，是指S中存在两个质数相关的数，否则称S为质数无关。如{2, 8, 17}质数无关，但{2, 8, 16}, {3, 6}质数相关。现在给定一个集合S，问S的所有质数无关子集中，最大的子集的大小。
输入 第一行为一个数T，为数据组数。之后每组数据包含两行。
第一行为N，为集合S的大小。第二行为N个整数，表示集合内的数。
输出 对于每组数据输出一行，形如”Case #X: Y”。X为数据编号，从1开始，Y为最大的子集的大小。
数据范围 1 ≤ T ≤ 20
集合S内的数两两不同且范围在1到500000之间。
小数据
1 ≤ N ≤ 15
大数据
1 ≤ N ≤ 1000
样例输入 3 5 2 4 8 16 32 5 2 3 4 6 9 3 1 2 3 样例输出 Case #1: 3 Case #2: 3 Case #3: 2
二分图。
容易想到把不符合条件的数字连边，问题转化成了求最大独立集。
求最大独立集不是np问题吗？
这道题有特殊的性质，他是一个二分图！！
因为二分图的充要条件是不存在奇环。 如果A,B与C质数相关，AB一定是质数无关的，所以不存在奇环。
即此图是二分图，直接匈牙利算法求最大匹配。
自己选择的路，跪着也要把它走完。
