a285. 女兒國婚友社
Tags : 有多項式時間算法,但是相當複雜。所以...?
Accepted rate : 38人/44人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-12 22:39

Content

 當唐三藏一行人走到女兒國時,八戒看到滿三遍野的女人,馬上全副武裝地去當地的婚友社報名,希望在離開前可以騙個開心的夜晚。可惜的是,八戒的下流招數這次一點都不管用了,因為女兒國當地根本就沒有男生,所以她們是同性結婚的!不過她們的同性戀愛並非GL式的浪漫戀情,實際上並沒有男女之分,所以隨便找兩個女生都是可以配對的。

        儘管八戒被拒於門外,但是婚友社的社長還是給了他一個很好的、可以親近女人的機會,就是請他來當她們的暫時工讀生。不幸的是,這工讀生的工作一點也不好當,因為最近婚友社正為了一個問題傷腦筋─儘管聽起來是很和善的機構,婚友社畢竟還是營利機構,希望自己可以賺到盡量多的錢。現在有 2n個( 0<n<=8 )顧客已經報名要參加徵婚了,這2n個女生每個都已經填好了一個表格,代表她對其它 2n-1個女生的好感度。為了方便起見,A對B的好感度跟B對A的好感度會是一樣的。已知好感度都是整數,並且湊合一對「情侶」賺的錢會是她們的好感度*10,那麼如何湊合這n對情侶就是一個值得思考的問題了。不過,要注意的是,可能會有兩個人互相討厭,這時候如果湊合她們就會導致她們傷心、難過、悲傷、氣憤、絕望、失落……到最後就會跳樓自殺,所以這時候反而要付她們賠償費。這些賠償費理所當然會影響到婚友社的收入。

        現在給你n,以及她們之間的好感度,你能幫八戒完成這個困難的任務嗎?

Input

第一行有一個整數n,以下有2n行,每行有2n個數字,分別表示顧客們之間的好感度。

特別的是,如果兩個人互相憎恨,她們的好感度就會是負數。自己對自己的好感度當然是0。

Output

輸出婚友社本期最大可能的收入。

Sample Input #1
2
0 1 2 3
1 0 2 3
2 2 0 3
3 3 3 0
Sample Output #1
50
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :

也就是湊合第一個人跟第四個人賺30元,第二個人跟第三個人賺20元。

Tags:
有多項式時間算法,但是相當複雜。所以...?
出處:
HKHS 練習賽II Problem C [管理者: b821213 (後繼無人) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」