poj-2411 Mondriaan's Dream ***

  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 <cstdio>
 39 #include <cstring>
 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<m; i++){
 51         if(((cur>>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<m; i++){
 64         if(!(cur&(1<<i))){
 65             if(!(last&(1<<i)))
 66                 return false;
 67         }
 68         else{
 69             if(!(last&(1<<i))) continue;
 70             if(i==m-1 || (!(last&(1<<(i+1)))) || (!(cur&(1<<(i+1)))) )
 71                     return false;
 72             i++;
 73         }
 74     }
 75     return true;
 76 }
 77 
 78 int main(){
 79     //    
 80     memset(ansRec, -1, sizeof(ansRec));
 81 
 82     while(scanf("%d%d", &n, &m)){
 83         if(n == 0) return 0;
 84 
 85         //  
 86         if((n % 2 != 0) && (m % 2 != 0)){
 87             printf("0
");
 88             continue;
 89         }
 90         //  
 91         if(ansRec[m][n] != -1){
 92             printf("%lld
", ansRec[m][n]);
 93             continue;
 94         }
 95         //       
 96         int tmp;
 97         if(n < m){
 98             tmp = n;
 99             n = m;
100             m = tmp;
101         }
102     
103         //   
104         memset(dp, 0, sizeof(dp));
105     
106         //the first line
107         for(int i=0; i<(1<<m); i++){
108             if(check(i))
109                 dp[0][i] = 1;
110         }
111     
112         //dp
113         for(int i=1; i<n; i++){
114             for(int j=0; j<(1<<m); j++){
115                 for(int k=0; k<(1<<m); k++)
116                     if(isOk(j, k)){
117                         dp[i][j] += dp[i-1][k];
118                     }
119             }
120         }
121     
122         printf("%lld
", dp[n-1][(1<<m)-1]);
123         ansRec[n][m] = ansRec[m][n] = dp[n-1][(1<<m)-1];
124     }
125 
126     return 0;
127 }

 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<cstdio>
23 #include<cstring>
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<<pos)&&!(s1&1<<pos+1)) sayatime(i,s1|1<<pos|1<<pos+1,pos+2);
30 }
31 int main()
32 {
33     
34     while(scanf("%d%d",&n,&m),n!=0)
35     {
36     memset(f,0,sizeof(f));saya=1;
37     sayatime(1,0,0);
38     for (i=2;i<=n;i++)
39     for (j=0;j<1<<m;j++)
40     {
41         if (f[i-1][j]) saya=f[i-1][j]; else continue;
42         sayatime(i,~j&((1<<m)-1),0);
43     }
44     printf("%lld
",f[n][(1<<m)-1]);
45     }
46 }

 1 /*
 2 p、c       
 3 */
 4 
 5 #include<iostream>
 6 #include<cstring>
 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<<m)-1]=1;
15     for (i=0;i<n;i++)
16         for (j=0;j<m;j++)
17         {
18             swap(p,c);memset(f[c],0,sizeof(f[c]));
19             for (ps=0;ps<1<<m;ps++)
20             if (f[p][ps])
21             {
22                 if (j>0&&(!(ps&(1<<j-1)))&&(ps&(1<<j))) f[c][ps|1<<(j-1)]+=f[p][ps];
23                 if (!(ps&1<<j)) f[c][ps|1<<j]+=f[p][ps];
24                 if (ps&1<<j) f[c][ps^1<<j]+=f[p][ps];
25             }
26         }
27     printf("%lld
",f[c][(1<<m)-1]);
28     }
29 }