UESTC_方老师买表 CDOJ 885

老师买表

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

由于方老师出色的专题讲座，他的名气迅速扩散到全国各地，并通过各地的讲座赚到了很多钱，鉴于现在盛行买表，于是方老师带上了一个

Input

输入有多组数据

每组数据占一行，每一行有

Output

对于每组测试数据输出

Sample input and output

Sample Input	Sample Output
2 10 3 3	89 0

Source

2014 UESTC Training for Dynamic Programming

解题报告

跟冬马党那题一样~,f(i,j)表示第i行摆成j样子的时候的总方案数.

转移的时候从最右边往最左边dp(正好跟二进制一样~).转移一共三种

假设正在转移第 pos 位,同时目前的摆放状态是 val (第 pos - 1 -- 第 0 位是这行的状态 , 第pos - 第 w 位还是上一行的状态)

if (val >> pos & 1 ) //上一行的这里摆了

转移至 val & ~(1 << pos) //这里可以不摆

if ( pos 不是最左边 && val >> (pos+1) & 1 ) // 现在可以左放

转移至 val ; //值是一样，但是含义不一样了哦

else

转移至 val | (1 << pos) //竖着放

这样就解决了~~

代码用了滚动数组,优化了空间复杂度

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 typedef long long ll;
 6 using namespace std;
 7 ll f[2][1 << 11];
 8 int h,w,cur = 0;
 9 
10 void dfs(int pos,int val,ll add)
11 {
12    if (pos == w)
13     f[cur][val] += add;
14    else
15     {
16        if (val >> pos & 1)
17         {
18            dfs(pos+1,val & ~(1 << pos) , add); //不放 
19            if (pos < w-1 && val >> (pos+1) &1) //左放
20             dfs(pos+2,val,add);    
21         }
22        else
23         dfs(pos+1,val | (1 << pos),add );     //竖着放 
24     }
25 }
26 
27 int main(int argc,char *argv[])
28 {
29   while(~scanf("%d%d",&h,&w))
30    {
31         memset(f,0,sizeof(f));
32      dfs(0,(1 << w)-1,1);
33      for(int i = 1 ; i < h ; ++ i)
34       {
35           cur ^= 1;
36           for(int i = 0 ; i < (1 << w) ; ++ i) f[cur][i] = 0;
37           for(int j = 0 ; j < (1 << w) ; ++ j)
38            dfs(0,j,f[cur^1][j]);
39       }
40      printf("%lld
",f[cur][(1<<w)-1]); 
41    }
42   return 0;
43 }

No Pain , No Gain.