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

逐行递推：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 #define eps 0.000000115 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<
                  
                   ans)60 ans = max(ans, dp[n][i]);61 62 printf("%d\n",ans);63 }64 return 0;65 }

View Code

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 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

View Code

简化后：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 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

View Code

轮廓线更新 + 哈希表：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 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 struct23 {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