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

时间：2023-03-08 21:14:03

题目链接：https://vjudge.net/problem/HDU-1565

方格取数(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

逐行递推：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = +;

 int n, a[][], sta[maxn], val[maxn], dp[][maxn];

 int tot;

 int cal(int r, int state)

 {

     int sum = ;

     for(int i = ; state>; state>>=, i++)

         if(state&)

             sum += a[r][i];

     return sum;

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         for(int i = ; i<=n; i++)

         for(int j = ; j<=n; j++)

             scanf("%d",&a[i][j]);

         tot = ;

         for(int i = ; i<(<<n); i++)

             if((i&(i<<))==)

                 sta[++tot] = i;

         memset(dp, , sizeof(dp));

         for(int r = ; r<=n; r++)

         {

             for(int j = ; j<=tot; j++)

             for(int k = ; k<=tot; k++)

             {

                 if((sta[j]&sta[k])==)

                     dp[r][j] = max(dp[r][j], dp[r-][k]+ cal(r,sta[j]));

             }

         }

         int ans = ;

         for(int i = ; i<=tot; i++)

         if(dp[n][i]>ans)

             ans = max(ans, dp[n][i]);

         printf("%d\n",ans);

     }

     return ;

 }

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e5;

 const int HASH = 1e4;

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

 int main()

 {

     while(scanf("%d", &n)!=EOF)

     {

         for(int i = ; i<n; i++)

         for(int j = ; j<n; j++)

             scanf("%d", &val[i][j]);

         int cur = ;

         for(int s = ; s<(<<n); s++)

             dp[cur][s] = -INF;

         dp[cur][] = ;

         for(int i = ; i<n; i++)

         for(int j = ; j<n; j++)

         {

             memset(dp[cur^], , sizeof(dp[cur^]));

             for(int s = ; s<(<<n); s++)

             {

                 bool hav_up = s&(<<j);

                 bool hav_left = false;

                 if(j) hav_left = s&(<<(j-));

                 if(!hav_up && !hav_left)

                 {

                     dp[cur^][s^(<<j)] = max(dp[cur^][s^(<<j)], dp[cur][s]+val[i][j]);   //取

                     dp[cur^][s] = max(dp[cur^][s], dp[cur][s]);       //不取

                 }

                 //由于相邻的格子已经去了，故此格子不能取

                 else if(hav_left && !hav_up)

                     dp[cur^][s] = max(dp[cur^][s], dp[cur][s]);

                 else if(!hav_left && hav_up)

                     dp[cur^][s^(<<j)] = max(dp[cur^][s^(<<j)], dp[cur][s]);

                 else

                     dp[cur^][s^(<<j)] = max(dp[cur^][s^(<<j)], dp[cur][s]);

             }

             cur ^= ;

         }

         int ans = ;

         for(int s = ; s<(<<n); s++)

             ans = max(ans, dp[cur][s]);

         printf("%d\n", ans);

     }

 }

简化后：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e5;

 const int HASH = 1e4;

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

 int main()

 {

     while(scanf("%d", &n)!=EOF)

     {

         for(int i = ; i<n; i++)

         for(int j = ; j<n; j++)

             scanf("%d", &val[i][j]);

         int cur = ;

         for(int s = ; s<(<<n); s++)

             dp[cur][s] = -INF;

         dp[cur][] = ;

         for(int i = ; i<n; i++)

         for(int j = ; j<n; j++)

         {

             memset(dp[cur^], , sizeof(dp[cur^]));

             for(int s = ; s<(<<n); s++)

             {

                 int up = s&(<<j);

                 int left = ;

                 if(j) left = s&(<<(j-));

                 dp[cur^][s^up] = max(dp[cur^][s^up], dp[cur][s]); //不取. （异或功能强大）

                 if(!up && !left)        //取，前提是相邻格没有取

                     dp[cur^][s^(<<j)] = max(dp[cur^][s^(<<j)], dp[cur][s]+val[i][j]);

             }

             cur ^= ;

         }

         int ans = ;

         for(int s = ; s<(<<n); s++)

             ans = max(ans, dp[cur][s]);

         printf("%d\n", ans);

     }

 }

轮廓线更新 + 哈希表：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e5;

 const int HASH = 1e4;

 int n, val[][];

 struct

 {

     int size, head[HASH], next[MAXN];

     int state[MAXN], sum[MAXN];

     void init()

     {

         size = ;

         memset(head, -, sizeof(head));

     }

     void insert(int status, int Sum)

     {

         int u = status%HASH;

         for(int i = head[u]; i!=-; i = next[i])

         {

             if(state[i]==status)

             {

                 sum[i] = max(sum[i], Sum);

                 return;

             }

         }

         state[size] = status;   //头插法

         sum[size] = Sum;

         next[size] = head[u];

         head[u] = size++;

     }

 }Hash_map[];

 int main()

 {

     while(scanf("%d", &n)!=EOF)

     {

         for(int i = ; i<n; i++)

         for(int j = ; j<n; j++)

             scanf("%d", &val[i][j]);

         int cur = ;

         Hash_map[cur].init();

         Hash_map[cur].insert(, );

         for(int i = ; i<n; i++)

         for(int j = ; j<n; j++)

         {

             Hash_map[cur^].init();

             for(int k = ; k<Hash_map[cur].size; k++)

             {

                 int status = Hash_map[cur].state[k];

                 int Sum = Hash_map[cur].sum[k];

                 int up = status&(<<j);

                 int left = ;

                 if(j) left = status&(<<(j-));

                 Hash_map[cur^].insert(status^up, Sum);     //不取

                 if(!up && !left)                //取，前提是相邻的格子没有取

                     Hash_map[cur^].insert(status^(<<j), Sum+val[i][j]);

             }

             cur ^= ;

         }

         int ans = ;

         for(int k = ; k<Hash_map[cur].size; k++)

             ans = max(ans, Hash_map[cur].sum[k]);

         printf("%d\n", ans);

     }

 }

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

HDU1569 方格取数(2)