题外话：今天刚学写了二分图最大权匹配KM算法，AC了1303。。其实回了匈牙利算法的话还是很容易上手的，发明算法的人顶标那个想法确实很有创意。线段树看懂了，还好有之前其他二叉树的基础，写树很长，但写起来时候挺爽~~1136自己没想到，囿于直接递推的思维。看了别人的题解一看到他的方程眼就亮了。。瞬间明白了实现方法。。说明自己还是缺乏创造力啊~~~过两天实现了它练手线段树~~
-------------------------------------------------------------------------------------------------------------------------------------------------------
思路：遇到这类题明显的就差方程而已。f[i]表示3*i的方案数。f[2]=3,f[i]=f[i-2]*3，这个是很容易想到的，但是存在交错的情况，这个是比较麻烦。。但我们自己画一下可以发现交错的时候交错那一块必会出现一个横排，这个横排出现在上排或下排，最重要的是交错排不会存在其他情况。因此一个交错快只会有两种情况。又因为交错快只会有偶数的情况，所以f[i]=3*f[i-2]+2*zigma(j=0~(i-4),2*f[j])。然后弄对了方程还是没弄出了答案。。后来发现忘了经常易错的f[0]=1。。。
改进：刚好习惯做完会搜一下看看别人的程序思路，看到了一种状态压缩DP的方法。在此也介绍一下
f[i][j]表示在1~i-1列都填满的时候第i列为第j种情况的方案数目。
对于第i列，只会出现以下5种情况。
for(int i=4;i<=31;i++) { f[i][0]+=f[i-2][0]; （i=1的情况没有两列） f[i][0]+=f[i-1][1]+f[i-1][2]; （情况1或情况2补一块竖直就成了情况0） f[i][1]=f[i-1][4]; （情况4上面补一个横块就成了i+1的情况1） f[i][2]=f[i-1][3]; （解释同上） f[i][3]+=f[i][0]+f[i-1][2]; （情况0在新一列补一个竖直块或情况2补两个横快） f[i][4]+=f[i-1][1]+f[i][0]; （解释同上） }
源程序和该方法出处请看http://iamhuangguan.blog.163.com/blog/static/124497319201011810819446/
感谢该位大牛。
但是那个初始化由于i从1开始所以初始化0意义不太明确，可以考虑初始化0,1,2,3的情况，i从4开始。
