題目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,y)$的金字塔覆蓋了x$x$軸的x?y$x-y$到x+y$x+y$這1段區間。

首先把金字塔依照左端點排序（x?y$x-y$），這1步非常關鍵！！

設f[i][j]$f[i][j]$表示前i$i$個金字塔，最多覆蓋到j$j$的最大獲利。

然后分3種情況轉移，即第i$i$個金字塔與j$j$大小關系:
①x[i]+y[i]≤j$x[i]+y[i]le j$
②x[i]?y[i]<j<x[i]+y[i]$x[i]-y[i] lt jlt x[i]+y[i]$
③j≤x[i]?y[i]$j le x[i]-y[i]$

還有1個轉移是只放第i$i$個這1種。

在前兩種情況中，我們可以保證第i$i$個金字塔≤j$le j$的部份之前已被覆蓋了（初始值為?inf$-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分圖，直接匈牙利算法求最大匹配。