方格取数(1)

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 8170    Accepted Submission(s): 3095

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

 

比较简单的状态压缩dp

1 //2016.9.8 2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 int arr[22][22]; 9 int dp[22][20000], sum[22][20000];//dp[i][j]表示第i行使用第j种方法所能得到的最大值，sum[i][j]表示第i行使用第j种方法所得的和10 int state[20000];//表示可行的状态，即可行的取数方法11 int len, n;12 13 bool ok(int sta)//可行状态，即1的位置两两不相邻14 {15     return (sta&(sta<<1))==0?true:false;16 }17 18 int get_sum(int pos, int x)//求第pos行，使用x方法能取得的和19 {20     int sum = 0, cnt = 1;21     while(x)22     {23         sum += (x%2)*arr[pos][n-cnt];24         x >>= 1;25         cnt++;26     }27     return sum;28 }29 30 void init(int m)//初始化31 {32     len = 0;33     for(int i = 0; i < (1<
          
           >n)46     {47         for(int i = 0; i < n; i++)48              for(int j = 0; j < n; j++)49                 scanf("%d", &arr[i][j]);50         init(n);51         for(int i = 1; i < n; i++)//处理第i行52             for(int j = 0; j < len; j++)//采取第j种方法53                 for(int k = 0; k < len; k++)//枚举上一行所采取的方法k54                     if((state[j]&state[k])==0)//方法j、k可行。ps：要加括号，&的优先级比==还低，debug了半天一脸懵逼，真是醉了55                         dp[i][j] = max(dp[i][j], dp[i-1][k]+sum[i][j]);//状态转移方程56 57         int ans = 0;58         for(int i = 0; i < len; i++)//找出最大值59             if(dp[n-1][i]>ans)60                   ans = dp[n-1][i];61 62         cout<
           
            <