LightOJ 1011 - Marriage Ceremonies （狀壓dp）

題意:

n∗n(n≤16)的矩陣aij表示i和j一對的權,求最大權完美比對的權

分析:

狀壓dp,dp[i][s]:=前i個男的,已選妹子狀态為s的最大權,暴力轉移就好了

嘛,跑一個km也是可以的

代碼:

//
//  Created by TaoSama on 2015-10-27
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N =  + , INF = , MOD =  + ;

int n, a[][], dp[][ << ];

int dfs(int i, int s) {
    int& ret = dp[i][s];
    if(i == n) return ;
    if(~ret) return ret;
    ret = ;
    for(int k = ; k < n; ++k) {
        if(s >> k & ) continue;
        ret = max(ret, dfs(i + , s |  << k) + a[i][k]);
    }
    return ret;
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    int t; scanf("%d", &t);
    int kase = ;
    while(t--) {
        scanf("%d", &n);
        for(int i = ; i < n; ++i)
            for(int j = ; j < n; ++j)
                scanf("%d", &a[i][j]);
        memset(dp, -, sizeof dp);
        printf("Case %d: %d\n", ++kase, dfs(, ));
    }
    return ;
}