本文共 1271 字，大约阅读时间需要 4 分钟。

题目链接：

第一次写状态压缩，感觉好强大，巧妙的运用二进制，不过不太熟练，参考了大牛的博客，想了想，恨牛叉的样子

题解：

#include
   
    #include
    
     #include
     
      using namespace std;int s[20000];int dp[30][20000];int map[30][30];int num;int n;bool ok(int x)//判断不相邻的情况{    if(x&(x>>1)) return false;//同一行存在相邻的情况    return true;}void init(int m){    num = 0;    for(int i = 0;i < m;i++)        if(ok(i)) s[num++] = i;}int cal(int x,int t)//计算该状态下的和{    int sum = 0, j = n - 1;    while(t)    {        if(t&1) sum += map[x][j];        j--;        t >>= 1;    }    return sum;}int main(){    while(~scanf("%d",&n))    {        if(n == 0) {puts("0");continue;}        init(1<
      
       < n;i++)        for(int j = 0;j < n;j++)            scanf("%d",&map[i][j]);        memset(dp,0,sizeof(dp));        for(int i = 0;i < num;i++)            dp[0][i] = cal(0,s[i]);        for(int i = 1;i < n;i++)        {            for(int j = 0;j < num;j++)            {                int tmp = cal(i,s[j]);                for(int k = 0;k < num;k++)                {                    if(s[j]&s[k]) continue;                    dp[i][j] = max(dp[i-1][k] + tmp,dp[i][j]);                }            }        }        int ans = 0;        for(int i = 0;i < num;i++)            ans = max(dp[n-1][i],ans);        printf("%d\n",ans);    }}
      
     
    
   

转载地址：http://ybsgi.baihongyu.com/