方格取数(1)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9929 Accepted Submission(s): 3743

Problem Description

给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

Input

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

3 75 15 21 75 15 28 34 70 5

Sample Output

188

Author

ailyanlu

Source

Happy 2007

逐行递推：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <stack>
11 #include <sstream>
12 #include <algorithm>
13 using namespace std;
14 #define eps 0.0000001
15 typedef long long LL;
16 const int INF = 2e9;
17 const LL LNF = 9e18;
18 const int mod = 1e9+7;
19 const int maxn = 17711+10;
20 
21 int n, a[25][25], sta[maxn], val[maxn], dp[25][maxn];
22 int tot;
23 
24 int cal(int r, int state)
25 {
26     int sum = 0;
27     for(int i = 1; state>0; state>>=1, i++)
28         if(state&1)
29             sum += a[r][i];
30     return sum;
31 }
32 
33 int main()
34 {
35     while(scanf("%d",&n)!=EOF)
36     {
37         for(int i = 1; i<=n; i++)
38         for(int j = 1; j<=n; j++)
39             scanf("%d",&a[i][j]);
40 
41         tot = 0;
42         for(int i = 0; i<(1<<n); i++)
43             if((i&(i<<1))==0)
44                 sta[++tot] = i;
45 
46         memset(dp, 0, sizeof(dp));
47         for(int r = 1; r<=n; r++)
48         {
49             for(int j = 1; j<=tot; j++)
50             for(int k = 1; k<=tot; k++)
51             {
52                 if((sta[j]&sta[k])==0)
53                     dp[r][j] = max(dp[r][j], dp[r-1][k]+ cal(r,sta[j]));
54             }
55         }
56 
57         int ans = 0;
58         for(int i = 1; i<=tot; i++)
59         if(dp[n][i]>ans)
60             ans = max(ans, dp[n][i]);
61 
62         printf("%d
",ans);
63     }
64     return 0;
65 }

View Code

逐格递推（轮廓线更新）：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e5;
18 const int HASH = 1e4;
19 
20 int n, val[25][25], dp[2][1<<21];
21 
22 int main()
23 {
24     while(scanf("%d", &n)!=EOF)
25     {
26         for(int i = 0; i<n; i++)
27         for(int j = 0; j<n; j++)
28             scanf("%d", &val[i][j]);
29 
30         int cur = 0;
31         for(int s = 0; s<(1<<n); s++)
32             dp[cur][s] = -INF;
33         dp[cur][0] = 0;
34 
35         for(int i = 0; i<n; i++)
36         for(int j = 0; j<n; j++)
37         {
38             memset(dp[cur^1], 0, sizeof(dp[cur^1]));
39             for(int s = 0; s<(1<<n); s++)
40             {
41                 bool hav_up = s&(1<<j);
42                 bool hav_left = false;
43                 if(j) hav_left = s&(1<<(j-1));
44 
45                 if(!hav_up && !hav_left)
46                 {
47                     dp[cur^1][s^(1<<j)] = max(dp[cur^1][s^(1<<j)], dp[cur][s]+val[i][j]);   //取
48                     dp[cur^1][s] = max(dp[cur^1][s], dp[cur][s]);       //不取
49                 }
50                 //由于相邻的格子已经去了，故此格子不能取
51                 else if(hav_left && !hav_up)
52                     dp[cur^1][s] = max(dp[cur^1][s], dp[cur][s]);
53                 else if(!hav_left && hav_up)
54                     dp[cur^1][s^(1<<j)] = max(dp[cur^1][s^(1<<j)], dp[cur][s]);
55                 else
56                     dp[cur^1][s^(1<<j)] = max(dp[cur^1][s^(1<<j)], dp[cur][s]);
57             }
58             cur ^= 1;
59         }
60 
61         int ans = 0;
62         for(int s = 0; s<(1<<n); s++)
63             ans = max(ans, dp[cur][s]);
64         printf("%d
", ans);
65     }
66 }

View Code

简化后：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e5;
18 const int HASH = 1e4;
19 
20 int n, val[25][25], dp[2][1<<21];
21 
22 int main()
23 {
24     while(scanf("%d", &n)!=EOF)
25     {
26         for(int i = 0; i<n; i++)
27         for(int j = 0; j<n; j++)
28             scanf("%d", &val[i][j]);
29 
30         int cur = 0;
31         for(int s = 0; s<(1<<n); s++)
32             dp[cur][s] = -INF;
33         dp[cur][0] = 0;
34 
35         for(int i = 0; i<n; i++)
36         for(int j = 0; j<n; j++)
37         {
38             memset(dp[cur^1], 0, sizeof(dp[cur^1]));
39             for(int s = 0; s<(1<<n); s++)
40             {
41                 int up = s&(1<<j);
42                 int left = 0;
43                 if(j) left = s&(1<<(j-1));
44 
45                 dp[cur^1][s^up] = max(dp[cur^1][s^up], dp[cur][s]); //不取. （异或功能强大）
46                 if(!up && !left)        //取，前提是相邻格没有取
47                     dp[cur^1][s^(1<<j)] = max(dp[cur^1][s^(1<<j)], dp[cur][s]+val[i][j]);
48             }
49             cur ^= 1;
50         }
51 
52         int ans = 0;
53         for(int s = 0; s<(1<<n); s++)
54             ans = max(ans, dp[cur][s]);
55         printf("%d
", ans);
56     }
57 }

View Code

轮廓线更新 + 哈希表：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e5;
18 const int HASH = 1e4;
19 
20 int n, val[25][25];
21 
22 struct
23 {
24     int size, head[HASH], next[MAXN];
25     int state[MAXN], sum[MAXN];
26 
27     void init()
28     {
29         size = 0;
30         memset(head, -1, sizeof(head));
31     }
32 
33     void insert(int status, int Sum)
34     {
35         int u = status%HASH;
36         for(int i = head[u]; i!=-1; i = next[i])
37         {
38             if(state[i]==status)
39             {
40                 sum[i] = max(sum[i], Sum);
41                 return;
42             }
43         }
44         state[size] = status;   //头插法
45         sum[size] = Sum;
46         next[size] = head[u];
47         head[u] = size++;
48     }
49 
50 }Hash_map[2];
51 
52 int main()
53 {
54     while(scanf("%d", &n)!=EOF)
55     {
56         for(int i = 0; i<n; i++)
57         for(int j = 0; j<n; j++)
58             scanf("%d", &val[i][j]);
59 
60         int cur = 0;
61         Hash_map[cur].init();
62         Hash_map[cur].insert(0, 0);
63         for(int i = 0; i<n; i++)
64         for(int j = 0; j<n; j++)
65         {
66             Hash_map[cur^1].init();
67             for(int k = 0; k<Hash_map[cur].size; k++)
68             {
69                 int status = Hash_map[cur].state[k];
70                 int Sum = Hash_map[cur].sum[k];
71 
72                 int up = status&(1<<j);
73                 int left = 0;
74                 if(j) left = status&(1<<(j-1));
75 
76                 Hash_map[cur^1].insert(status^up, Sum);     //不取
77                 if(!up && !left)                //取，前提是相邻的格子没有取
78                     Hash_map[cur^1].insert(status^(1<<j), Sum+val[i][j]);
79             }
80             cur ^= 1;
81         }
82 
83         int ans = 0;
84         for(int k = 0; k<Hash_map[cur].size; k++)
85             ans = max(ans, Hash_map[cur].sum[k]);
86         printf("%d
", ans);
87     }
88 }

View Code

二分图点带权最大独立集（最小割最大流）：

HDU1565 方格取数(1) —— 状压DP or 插头DP（轮廓线更新） or 二分图点带权最大独立集（最小割最大流）

方格取数(1)

HDU1569 方格取数(2)