题意：
         给定一个n*n  (n<=20) 的方格，里头放有一些非负数，选择一些不相邻的格子，使其和最大。
分析：
         主要思想是从第一行到第N行，从第一列到第N列进行DP，用位来保存状态，比如在i行j列，对所有的0到2^n  -1 状态进行计算，最后的结果是从i=n-1,j=n-1的2^n个状态求最大就OK了。别以为这运算量很大，其实只有O(n*n*2^n)比直接暴搜O(n!*n!)快了N多，因为这题数据比较小，N最大为20，所以可以这么DP。但如果N很大的话这种方法显然不行，那就要用到最大流了。
        

 1#include<iostream>
 2using namespace std;
 3
 4const int mm=1<<20+1;
 5int rect[51][51];
 6int dp[2][mm];
 7int maxn=-1;
 8int n;
 9
10int solve()
11{
12   int i,j,k,p,t,z;
13   for(i=0;i<n;i++)
14   {         
15       for(j=0;j<n;j++)
16       {   
17           t=1<<j;
18           p=(i*n+j)%2;
19           for(k=0;k<(1<<n);k++)
20           {
21               if((k&t)==0)
22                   dp[1-p][k]=dp[p][k]>dp[p][k+t]? dp[p][k]:dp[p][k+t];
23               else if(j>0&&(k&(t>>1)))dp[1-p][k]=0;
24               else dp[1-p][k]=dp[p][k-t]+rect[i][j];
25           }
26       }
27   }
28   return 0;
29}
30
31int main()
32{
33    int i,j;
34    while(EOF!=scanf("%d",&n))
35    {   
36        for(i=0;i<n;i++)
37           for(j=0;j<n;j++)
38                scanf("%d",&rect[i][j]);
39        maxn=-1;
40        memset(dp,0,sizeof(dp));
41        solve();
42        for(i=0;i<(1<<n);i++)
43        {
44           if(dp[(n*n)%2][i]>maxn)
45               maxn=dp[(n*n)%2][i];
46        }
47        printf("%d\n",maxn);
48    }
49    return 0;
50}