題目2 : 建造金字塔

時(shí)間限制:4000ms
單點(diǎn)時(shí)限:2000ms
內(nèi)存限制:256MB
描寫
在2次元中，金字塔是1個(gè)底邊在x軸上的等腰直角3角形。

你是2次元世界的1個(gè)建筑承包商。現(xiàn)在有N個(gè)建造定單，每一個(gè)定單有1個(gè)收益w，即建造此金字塔可取得w的收益。對(duì)每一個(gè)定單可以選擇建造或不建造。

建造1個(gè)金字塔的本錢是金字塔的面積，如果兩個(gè)或多個(gè)金字塔有堆疊面積，則建造這些金字塔時(shí)堆疊部分僅需建造1次。

建造1組金字塔的總利潤是收益總和扣除本錢?，F(xiàn)給出這些定單，要求出最大利潤。

輸入
輸入數(shù)據(jù)第1行動(dòng)1個(gè)整數(shù)T，表示數(shù)據(jù)組數(shù)。

每組數(shù)據(jù)第1行動(dòng)1個(gè)整數(shù)N，表示定單數(shù)目。

接下來N行，每行3個(gè)整數(shù)x, y, w，表示1個(gè)定單。(x, y)表示建造出的金字塔的頂點(diǎn)，w表示收益。

輸出
對(duì)每組數(shù)據(jù)輸出1行”Case #X: Y”，X表示數(shù)據(jù)編號(hào)（從1開始），Y表示最大利潤，4舍5入到小數(shù)點(diǎn)后兩位。

數(shù)據(jù)范圍
1 ≤ T ≤ 20

0 ≤ w ≤ 107

小數(shù)據(jù)

1 ≤ N ≤ 20

0 ≤ x, y ≤ 20

大數(shù)據(jù)

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。

頂點(diǎn)為(x,y)$(x,y)$的金字塔覆蓋了x$x$軸的x?y$x-y$到x+y$x+y$這1段區(qū)間。

首先把金字塔依照左端點(diǎn)排序（x?y$x-y$），這1步非常關(guān)鍵?。?/p>

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

然后分3種情況轉(zhuǎn)移，即第i$i$個(gè)金字塔與j$j$大小關(guān)系:
①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個(gè)轉(zhuǎn)移是只放第i$i$個(gè)這1種。

在前兩種情況中，我們可以保證第i$i$個(gè)金字塔≤j$le j$的部份之前已被覆蓋了（初始值為?inf$-inf$），由于是依照左端點(diǎn)排序的?。。∫蚨询B面積就很好算了。

題目3 : 質(zhì)數(shù)相干

時(shí)間限制:2000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
描寫
兩個(gè)數(shù)a和 b 被稱為質(zhì)數(shù)相干，是指a × p = b，這里p是1個(gè)質(zhì)數(shù)。1個(gè)集合S被稱為質(zhì)數(shù)相干，是指S中存在兩個(gè)質(zhì)數(shù)相干的數(shù)，否則稱S為質(zhì)數(shù)無關(guān)。如{2, 8, 17}質(zhì)數(shù)無關(guān)，但{2, 8, 16}, {3, 6}質(zhì)數(shù)相干。現(xiàn)在給定1個(gè)集合S，問S的所有質(zhì)數(shù)無關(guān)子集中，最大的子集的大小。

輸入
第1行動(dòng)1個(gè)數(shù)T，為數(shù)據(jù)組數(shù)。以后每組數(shù)據(jù)包括兩行。

第1行動(dòng)N，為集合S的大小。第2行動(dòng)N個(gè)整數(shù)，表示集合內(nèi)的數(shù)。

輸出
對(duì)每組數(shù)據(jù)輸出1行，形如”Case #X: Y”。X為數(shù)據(jù)編號(hào)，從1開始，Y為最大的子集的大小。

數(shù)據(jù)范圍
1 ≤ T ≤ 20

集合S內(nèi)的數(shù)兩兩不同且范圍在1到500000之間。

小數(shù)據(jù)

1 ≤ N ≤ 15

大數(shù)據(jù)

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分圖。

容易想到把不符合條件的數(shù)字連邊，問題轉(zhuǎn)化成了求最大獨(dú)立集。

求最大獨(dú)立集不是np問題嗎？

這道題有特殊的性質(zhì)，他是1個(gè)2分圖?。?/p>

由于2分圖的充要條件是不存在奇環(huán)。
如果A,B與C質(zhì)數(shù)相干，AB1定是質(zhì)數(shù)無關(guān)的，所以不存在奇環(huán)。

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