a285. 女兒國婚友社
內容 ：
當唐三藏一行人走到女兒國時，八戒看到滿三遍野的女人，馬上全副武裝地去當地的婚友社報名，希望在離開前可以騙個開心的夜晚。可惜的是，八戒的下流招數這次一點都不管用了，因為女兒國當地根本就沒有男生，所以她們是同性結婚的！不過她們的同性戀愛並非GL式的浪漫戀情，實際上並沒有男女之分，所以隨便找兩個女生都是可以配對的。
儘 管八戒被拒於門外，但是婚友社的社長還是給了他一個很好的、可以親近女人的機會，就是請他來當她們的暫時工讀生。不幸的是，這工讀生的工作一點也不好當， 因為最近婚友社正為了一個問題傷腦筋─儘管聽起來是很和善的機構，婚友社畢竟還是營利機構，希望自己可以賺到盡量多的錢。現在有 2n個（ 0<n<=8 ）顧客已經報名要參加徵婚了，這2n個女生每個都已經填好了一個表格，代表她對其它 2n-1個女生的好感度。為了方便起見，A對B的好感度跟B對A的好感度會是一樣的。已知好感度都是整數，並且湊合一對「情侶」賺的錢會是她們的好感度*10，那麼如何湊合這n對情侶就是一個值得思考的問題了。不過，要注意的是，可能會有兩個人互相討厭，這時候如果湊合她們就會導致她們傷心、難過、悲傷、氣憤、絕望、失落……到最後就會跳樓自殺，所以這時候反而要付她們賠償費。這些賠償費理所當然會影響到婚友社的收入。
現在給你n，以及她們之間的好感度，你能幫八戒完成這個困難的任務嗎？
輸入說明
：
第一行有一個整數n，以下有2n行，每行有2n個數字，分別表示顧客們之間的好感度。
特別的是，如果兩個人互相憎恨，她們的好感度就會是負數。自己對自己的好感度當然是0。
輸出說明
：
輸出婚友社本期最大可能的收入。
範例輸入 ：
2 0 1 2 3 1 0 2 3 2 2 0 3 3 3 3 0
範例輸出 ：
50
提示
：
也就是湊合第一個人跟第四個人賺30元，第二個人跟第三個人賺20元。
出處
：
/**********************************************************************************/
/* Problem: a285 "女兒國婚友社" from HKHS 練習賽II Problem C */
/* Language: C (778 Bytes) */
/* Result: AC(0ms, 362KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 22:36:56 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 100000
int map[16][16], Best[65537];
int n, i, j;
int DP(int N, int sum) {
if(N == 0) return 0;
if(Best[N] != -oo)
return Best[N];
if(Best[sum] == -oo)
Best[sum] = DP(sum, 0);
int i, j, tmp;
for(i = 0; i < n; i++) {
if(N&(1<<i)) {
for(j = i+1; j < n; j++) {
if(N&(1<<j)) {
tmp = DP(N-(1<<i)-(1<<j), sum+(1<<i)+(1<<j));
Best[N] = Best[N] > tmp+map[i][j] ? Best[N] : tmp+map[i][j];
}
}
break;
}
}
return Best[N];
}
int main() {
while(scanf("%d", &n) == 1) {
n *= 2;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &map[i][j]);
for(i = (1<<n)-1; i >= 0; i--)
Best[i] = -oo;
printf("%d\n", DP((1<<n)-1, 0)*10);
}
return 0;
}
下一篇：a275. 字串變變變