zoj 3471(状压DP)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}

------ 本文结束 ------