zoj 3471(状压DP)

zoj 3471
比较基础的状压，看题目数据才$n<=10$，果断状压。
用十位二进制来存储分子的存在情况，$1$为存在，$0$为不存在
设$dp(S)$为状态为$S$的最优值。
$$dp(S) = max(dp(S+j)+map(i, j))$$
注意因为是从$1$多向$1$少来转移，所以要倒推。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10 + 2; 
int n, ma[MAXN][MAXN], dp[1<<MAXN];
void clean() {}
void solve() {
    clean();
    for (int i=1;i<=n;i++) 
    for (int j=1;j<=n;j++) scanf("%d", &ma[i][j]);
    ms(dp, 0);
    for (int S=(1<<n)-1;S>0;S--) {//倒推，因为是从1多向1少来转移 
        for (int i=1;i<=n;i++) {
            if (S&(1<<(i-1))) {
                for (int j=1;j<=n;j++) {
                    if (i!=j&&!(S&(1<<(j-1)))) {
                        dp[S] = max(dp[S], dp[S^(1<<(j-1))]+ma[i][j]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i=1;i<=n;i++) {
        ans = max(ans, dp[1<<(i-1)]);
    }
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n)==1&&n) solve();
    return 0;
}