方格取数(1)

375 15 21 75 15 28 34 70 5  Sample Output
188 Authorailyanlu SourceHappy 2007 Recommend8600
题目大意：取不能有临边的点，求最大和
分析：把每一列转化为2进制每一位，1表示这个格子取，0为不取，通过二进制得到的整数值表示一个状态。
这边判断没有临边的方法即x&y==0同时x与y的二进制也没有相邻的1。即x&(x<<1)==0
用dp[i][j]表示第i行状态为j的最大和，那么它是由前面的i-1行的状态过来的。
方程为：dp[i][j]=max{dp[i][j],dp[i-1][k]+sum[j]}其中sum[j]表示在i行的状态为j取到数的和
 最后结果为max{dp[n][i]} i为状态
#include<stdio.h>#include<iostream>#include<string.h>using namespace std;int b[1000];int a[22][22];int dp[22][19000];int main(){    int n;    while(scanf("%d",&n)!=-1)    {        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                scanf("%d",&a[i][j]);            }        }        memset(dp,0,sizeof(dp));        int maxn=1<<n;        int p=0;        for(int i=0;i<maxn;i++)        {            if((i&i<<1)==0)            {                b[p++]=i;            }        }        for(int i=1;i<=n;i++)        {            for(int j=0;j<p;j++)            {                int sum=0;                for(int k=0;k<n;k++)//计算这个状态下的值                {                    if((b[j]&(1<<k)))//只要这个状态中第k+1位为1则取当前的值                    {                        sum+=a[i][k+1];                    }                }                dp[i][j]=sum;                for(int ha=0;ha<p;ha++)//和i-1行的各种状态比较，找出最大的                {                    if((b[j]&b[ha])==0)                    dp[i][j]=max(dp[i-1][ha]+sum,dp[i][j]);                }            }        }        int ma=-1;        for(int i=0;i<p;i++)        {            ma=max(ma,dp[n][i]);        }        printf("%d/n",ma);    }}