蓝桥杯算法提高VIP-金陵十三钗 （C语言代码）

解题思路: 

动态规划+状态压缩 ： 把 取 与不取 状态 为 1，0；状态 （从右向左）取 1 和 3（0101）压缩成 5 

原文
注意事项:

参考代码:

#include<stdio.h>
long int n_one;
int a[14][14],dp[1<<13]={0};//记录 当前 状态最优解 如 dp[5]=26 (0101状态下 最优解为 26) 
long int ma(int a,int b)
{if(a>b)return a;
  else return b;
}

long int jl_one(int a)//记录 当前 含 1 的个数 
{ long int c=0;
   while(a)
   {   if(a%2==1)c++;
       a=a/2;
   }
   return c;
}
long int wz_one(long int a)// 找出 从左向右数最后一个 1 的位置 如 4 100 返回 3； 
{int wz=0;
     while(a)
     { wz++;
     if(a%2==1)break;
        a=a/2;
     }
     return wz;
}
void f(int x)
{  int i,t,t2,pos;
for(i=0;i<n_one;i++)
  { t=jl_one(i);t2=i;
  if(t==x) //第x位女人有x个1，不是就继续找下一个数
         while(t--)
         {  pos=t2&(-t2);// 位运算 得从左向右最后一位 为 1 的值 如 5（101）返回 1； 
           dp[i]=ma(dp[i],dp[i-pos]+a[x][wz_one(pos)]);//按 5（101）从右向左依此更新 
            t2=t2-pos;
         }
  } 
}

int main()
{
   int i,j,n,m;

   scanf("%ld",&n);
   for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    n_one=1<<n;
    for(i=1;i<=n;i++)
       f(i);

  printf("%ld\n",dp[n_one-1]);// dp[n_one-1] 状态n_one-1（1111） 

return 0;
}