hdu 2167(状态压缩基础题)

题意：给你一个矩阵，让你在矩阵中找一些元素使它们加起来和最大，但是当你使用某一个元素时，那么这个元素周围的其它八个元素都不能取！

分析：这是一道比较基础的状态压缩题，也是我做的第三道状态压缩的题，但是这个题目的输入确实让我很无语，开始的时候wa一次，后来改成了超时，最后还是参照别人的输入ac的！

代码实现：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,map[][],dp[][(<<)+];
int a[],num;void chushihua()
{
    int i,max=<<;
    for(i=; i<max; i++)
        if((i&(i<<))==)
            a[num++]=i;
}int qiu(int r,int flag)
{
    int i,sum=,x=<<(n-);
    for(i=; i<=n; i++)
    {
        if((flag&x)!=)
            sum=sum+map[r][i];
        x=x>>;
    }
    return sum;
}void solve()
{
    int res=,i,j,k,p=,max,temp;
    max=<<n;
    memset(dp,,sizeof(dp));
    for(i=; i<=n; i++)
    {
        p=p^;
        memset(dp[p],,sizeof(dp[p]));
        for(j=; j<num&&a[j]<max; j++)
        {
            temp=qiu(i,a[j]);
            for(k=; k<num&&a[k]<max; k++)
            {
                if(((a[j]&a[k])==)&&(((a[j]<<)&a[k])==)&&(((a[j]>>)&a[k])==))
                {
                    if(dp[p][a[j]]<(temp+dp[-p][a[k]]))
                        dp[p][a[j]]=temp+dp[-p][a[k]];
                    if(res<dp[p][a[j]])
                        res=dp[p][a[j]];
                }
            }
        }
    }
    printf("%d\n",res);
}int main()
{
    char ch[],temp;
    num=;
    chushihua();
    while(gets(ch))
    {
        int i , j ;
        i =  ;
        do
        {
            if(ch[] == )    break ;
            int len = strlen(ch);
            j =  ;
            i++ ;
            for(int c=; c<len; c++)
            {
                if(ch[c] == ' ')    continue ;
                j++ ;
                map[i][j] = *(ch[c]-'') + ch[c+]-'' ;
                c++ ;
            }
        }
        while(gets(ch)!=NULL) ;
        n = i ;
        solve();
    }
    return ;
}