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


后来因为一个小小的弱智的错误 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;
}


打赏
未经允许不得转载:XINDOO » light oj 1011 – Marriage Ceremonies (状态压缩+记忆化搜索)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏