牛客比赛-状压dp

链接：https://www.nowcoder.com/acm/contest/74/F
来源：牛客网

德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。

这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。

有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。

结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土

地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标

记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他

们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西

亚英雄的方法？

输入描述:

输入包含多组测试数据；
每组数据的第一行包含2个整数n和m (n <= 12, m <= 12 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的比尔吉沃特领土。

输出描述:

输出一个整数n代表安排应用的方法。
（答案取膜100000000）

示例1

输入

输出

24
  比赛时想到状压dp，但没心情写了，刚才试了试1A了= =今天也算写了一题
  0一定是0,1有可能是1也有可能是0，用轮廓线处理就好了，复杂度O(n*m*m*2^m)
  一直没写卡在如何使最高位归零真是zz了，1xxxx,&上一个01111就好了。
  最后记得注意边界处理。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 LL mod=;

 int e[][];

 LL dp[][(<<)+];

 int main()

 {

     int n,m,i,j,k,p;

     while(cin>>n>>m){

         for(i=;i<n;++i)

             for(j=;j<m;++j) cin>>e[i][j];

         int cur=;

         memset(dp,,sizeof(dp));

         dp[][]=;

         for(i=;i<n;++i)

         {

             for(j=;j<m;++j)

             {

                 cur^=;

                 memset(dp[cur],,sizeof(dp[cur]));

                 for(k=;k<(<<m);++k)

                 {

                    dp[cur][(k<<)&((<<m)-)]=(

                    dp[cur][(k<<)&((<<m)-)]+dp[cur^][k]%mod)%mod;

                    if(e[i][j]){

                    if(j==){

                       if(!(k&(<<(m-))))

                       dp[cur][(k<<)&((<<m)-)|]=

                       (dp[cur][(k<<)&((<<m)-)|]+dp[cur^][k])%mod;

                    }

                    else{

                       if(!(k&(<<(m-))))

                       {

                           if(!(k&)){

                             dp[cur][(k<<)&((<<m)-)|]=

                       (dp[cur][(k<<)&((<<m)-)|]+dp[cur^][k])%mod;

                           }

                       }

                    }

                    }

                 }

             }

         }

         LL ans=;

         for(k=;k<(<<m);++k)ans=(ans+dp[cur][k])%mod;

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

牛客比赛-状压dp

输入描述:

输出描述:

输入

输出

最新文章

热门文章