蓝桥杯算法提高VIP-金陵十三钗 （C++代码）（状压Dp）

解题思路:
        

        ovo

参考代码:

#include <bits/stdc++.h>
constexpr auto Inf = 0x3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
    inline LL read() {
        LL o = 0, f = 1; char c = getchar();
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
        return o * f;
    }
    inline char recd() {
        char o; while ((o = getchar()) != 'C' && o != 'P'); return o;
    }
}
using namespace IO;

const int SIZE = 17;
int Arr[SIZE][SIZE], F[SIZE], Dp[SIZE][1 << SIZE], Ind[SIZE], M;

int BIT(int pos) {
	int ans = 0; while (pos) pos >>= 1, ans++; return ans;
}

int main() {
	scanf("%d", &M);
	for (int pos = 0; pos < M; pos++)
		F[pos] = 1 << pos, Ind[pos] = BIT(F[pos]);

	for (int posx = 1; posx <= M; posx++)
		for (int posy = 1; posy <= M; posy++)
			scanf("%d", &Arr[posx][posy]);

	for (int pos = 0; pos < M; pos++)
		Dp[1][F[pos]] = Arr[1][Ind[pos]];

	for (int pos = 2; pos <= M; pos++)
		for (int Status = 0; Status < M; Status++)
			for (int now = 1; now < 1 << M; now++)
				if (!(now & F[Status]))
					Dp[pos][F[Status] ^ now] = max(Dp[pos][F[Status] ^ now], 
					Dp[pos - 1][now] + Arr[pos][Ind[Status]]);

	printf("%d\n", Dp[M][(1 << M) - 1]);
}