编程之美2015初赛第一场BC

题目2 : 建造金字塔

时间限制:4000ms
单点时限:2000ms
内存限制:256MB
描写
在2次元中，金字塔是1个底边在x轴上的等腰直角3角形。

你是2次元世界的1个建筑承包商。现在有N个建造定单，每一个定单有1个收益w，即建造此金字塔可取得w的收益。对每一个定单可以选择建造或不建造。

建造1个金字塔的本钱是金字塔的面积，如果两个或多个金字塔有堆叠面积，则建造这些金字塔时堆叠部分仅需建造1次。

建造1组金字塔的总利润是收益总和扣除本钱。现给出这些定单，要求出最大利润。

输入
输入数据第1行动1个整数T，表示数据组数。

每组数据第1行动1个整数N，表示定单数目。

接下来N行，每行3个整数x, y, w，表示1个定单。(x, y)表示建造出的金字塔的顶点，w表示收益。

输出
对每组数据输出1行”Case #X: Y”，X表示数据编号（从1开始），Y表示最大利润，4舍5入到小数点后两位。

数据范围
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。

顶点为$(x,y)$的金字塔覆盖了$x$轴的$x-y$到$x+y$这1段区间。

首先把金字塔依照左端点排序（$x-y$），这1步非常关键！！

设$f[i][j]$表示前$i$个金字塔，最多覆盖到$j$的最大获利。

然后分3种情况转移，即第$i$个金字塔与$j$大小关系:
①$x[i]+y[i]le j$
②$x[i]-y[i] lt jlt x[i]+y[i]$
③$j le x[i]-y[i]$

还有1个转移是只放第$i$个这1种。

在前两种情况中，我们可以保证第$i$个金字塔$le j$的部份之前已被覆盖了（初始值为$-inf$），由于是依照左端点排序的！！！因而堆叠面积就很好算了。

题目3 : 质数相干

时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描写
两个数a和 b 被称为质数相干，是指a × p = b，这里p是1个质数。1个集合S被称为质数相干，是指S中存在两个质数相干的数，否则称S为质数无关。如{2, 8, 17}质数无关，但{2, 8, 16}, {3, 6}质数相干。现在给定1个集合S，问S的所有质数无关子集中，最大的子集的大小。

输入
第1行动1个数T，为数据组数。以后每组数据包括两行。

第1行动N，为集合S的大小。第2行动N个整数，表示集合内的数。

输出
对每组数据输出1行，形如”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

2分图。

容易想到把不符合条件的数字连边，问题转化成了求最大独立集。

求最大独立集不是np问题吗？

这道题有特殊的性质，他是1个2分图！！

由于2分图的充要条件是不存在奇环。
如果A,B与C质数相干，AB1定是质数无关的，所以不存在奇环。

即此图是2分图，直接匈牙利算法求最大匹配。