xindoo is
always here

# light oj 1011 – Marriage Ceremonies (状态压缩+记忆化搜索)

大概题意是有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;
}


//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;
}


• QQ咨询
• 回顶