LightOJ 1011 Marriage Ceremonies【状压DP】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/46380573

题目链接： http://www.lightoj.com/volume_showproblem.php?problem=1011

状态压缩DP；

dp[i][j] 表示在前i行man，状态j时的最大解。若j的第k位是1，则表示选择了第k个woman，否则表示没选择第k个woman。

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>
#include <iterator>
#include <vector>

using namespace std;

const int MAXN = 17;
int t;
int n,p[MAXN][MAXN];
int dp[MAXN][(1<<MAXN)];

int main()
{
    scanf("%d",&t);
    for(int cases =1;cases<=t;cases++)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&p[i][j]);
        memset(dp,0,sizeof(dp));
        int len = (1<<n);
        for(int i=0;i<n;i++) dp[0][1<<i] = p[0][i];
        for(int i=1;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {   
                    for(int k=0;k<len;k++)
                    {
                        if(!dp[i-1][k] || (1<<j)&k) continue;//k未选择过 或 jk都已经选择过
                        //也就是保证： k选择过 且 j没有被选择过
                        dp[i][(1<<j)|k] = max(dp[i][(1<<j)|k],dp[i-1][k] + p[i][j]);
                    }
                }
            }
        printf("Case %d: %d\n",cases,dp[n-1][len-1]);
    }
    return 0;
}