大概题意是有n个男的n个女的（原谅我这么说，我是粗人），给你一个n*n的矩阵，第i行第j列表示第i个女（男）对第j个男（女）的好感度，然后要安排n对相亲，保证都是正常的（无搞基百合之类的），然后求怎么安排能使好感度和最大，求出最大值。
开始试了纯暴力的方法，时间复杂度是n！果断超时
#include <iostream> #include <string.h> #include <algorithm> using namespace std; int vis[17]; int n, ans, sum; int map[19][19]; void dfs(int x) { if (x == n+1) { ans = max(ans, sum); return; } for (int i = 1; i <= n; i++) { if (vis[i] == 0) { sum += map[x][i]; vis[i] = 1; dfs(x+1); vis[i] = 0; sum -= map[x][i]; } } } int main() { int t; cin >> t; for (int kase = 1; kase <= t; kase++) { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> map[i][j]; sum = 0; ans = 0; memset(vis, 0, sizeof(vis)); dfs(1); cout << "Case " << kase << ": " << ans << endl; } return 0; }
后来因为一个小小的弱智的错误 wa了5 6次。代码中用了很多位运算，通过位运算很方便的把状态进行了压缩存储起来。
//2013-06-25-22.05 #include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; const int maxn = 1<<16; int vis[17]; int n, ans, sum; int map[19][19]; int dp[maxn]; int dfs(int x, int d) { if (x == 0) return 0; if (dp[x]) return dp[x]; for (int i = 0; i < n; i++) { if (x&(1<<i)) dp[x] = max(dfs(x^(1<<i), d-1)+map[i+1][d], dp[x]); } return dp[x]; } int main() { int t; cin >> t; for (int kase = 1; kase <= t; kase++) { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> map[i][j]; memset(dp, 0, sizeof(dp)); ans = dfs((1<<n)-1, n); printf("Case %d: %d\n", kase, ans); } return 0; }
