1 /* 状态压缩DP ， 类似炮兵阵地（POJ1185，本blog有。。）   2  *    3  *  自己写的，判断是否合法写的很长。。。   4  *   5  *  贴个"解题报告"吧。。   6  *      7 Assume you could calculate the number of different paintings   8 for a rectangle with c columns and r rows where the first r-1   9 rows are completely filled and the last row has any of 2c  10 possible patterns. Then, by trying all variations of filling  11 the last row where small rectangles may be spilled into a further  12 row, you can calculate the number of different paintings for a  13 rectangle with r+1 rows where the first r rows are completely  14 filled and the last row again has any pattern.  15  16 This straightforwardly leads to a dynamic programming solution.  17 All possible ways of filling a row part of which may already be  18 occupied and spilling into the next row creating a new pattern  19 are genrated by backtracking over a row. Viewing these as  20 transitions from a pattern to another pattern, their number  21 is given by the recursive equation Tc = 2 Tc-1 + Tc-2. Its  22 solution is asymptotically exponential with a base of sqrt(2)+1,  23 which is not a problem for c<=11.  24  25 If both h and w are odd, the result is 0. Since the number of  26 paintings is a symmetric function, the number of columns  27 should be chosen as the smaller of the two input numbers  28 whenever possible to improve run-time behaviour substantially.  29  30 Judges' test data includes all 121 legal combinations of h and w.  31  *   32  *  33  * 后面贴两个暴强25行代码（见POJ discuss）  34  *  35  *  36  */  37  38 #include 
     
        39 #include 
      
         40 using namespace std;  41  42 const int maxs = (1 << 11) + 5;  43 const int maxn = 11 + 3;  44  45 int n, m;  46 long long dp[maxn][maxs];  47 long long ansRec[maxn][maxn];  48  49 bool check(int cur){
    50     for(int i=0; i
       
        >i)&1)){
    52             if(i==m-1 || (!((cur)>>(i+1)&1)))  53                 return false;  54             i++;  55         }  56     }  57     return true;  58 }  59  60 //cur: 当前行状态  61 //last：上一行状态  62 bool isOk(int cur, int last){
    63     for(int i=0; i
       
      
     

　　

//25行代码-1

1 /*  2 用2进制的01表示不放还是放  3 第i行只和i-1行有关  4 枚举i-1行的每个状态，推出由此状态能达到的i行状态  5 如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块，  6 所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态。  7 然后用搜索扫一道在i行放横着的方块的所有可能，  8 并且把这些状态累加上i-1的出发状态的方法数，如果该方法数为0，  9 直接continue。 10 11 举个例子 12 2 4 13 1111 14 1111 15 状态可以由 16 1100 0000 0110 0011 1111 17 0000 0000 0000 0000 0000 18 这五种i-1的状态达到，故2 4 的答案为5 19 20 */ 21 22 #include
     
       23 #include
      
        24 long long f[30][1<<12],i,j,n,m,saya=1; 25 void sayatime (int i,int s1,int pos) 26 {
   27     if (pos==m) {f[i][s1]+=saya;return;} 28     sayatime(i,s1,pos+1); 29     if (pos<=m-2&&!(s1&1<
       
        <
       
      
     

　　

//25行代码-2

1 /*  2 p、c是滚动数组下标  3 */  4  5 #include
     
        6 #include
      
         7 using namespace std;  8 long long f[2][1<<12],i,j,ps,p=0,c=1,n,m;  9 int main() 10 {
   11     while (scanf("%d%d",&n,&m),n!=0) 12     {
   13     memset(f[c],0,sizeof(f[c])); 14     f[c][(1<
       
        0&&(!(ps&(1<
        
         <