hdu 1992 Tiling a Grid With Dominoes

本文主要是介绍hdu 1992 Tiling a Grid With Dominoes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1992

这题开始跟着别人的博客做，怎么也没想象到思路，搜了题解也没有看明白，没办法，只有自己想了……

一个大概的思路是根据前面已经的答案来递推，如果只加入1列的话，当然dp[n] + =dp[n-1] ,如果只加入2列的话，并且不以前一个为后缀的话就只有四个，在递推加入3列的情况，并且不以前第1个和第2个为后缀，我们分一下三种情况讨论：

  1） 如果最后一列是4个都是着的，那么必然以加入1列的情况重合；

  2） 如果最后一列是2个横着的，一个竖着的，存在两种情况，就不画图了

  3） 如果都是横着的，那么必然以加入2列的情况重合；

同理减少偶数列 dp[n]+=3*dp[i];

#include <cstdlib>
#include <iostream>using namespace std;long long dp[1010];int main(int argc, char *argv[])
{dp[0]=1;dp[1]=1;dp[2]=5;//dp[3]=11;for(int i=3;i<=1000;i++){dp[i]=dp[i-1]+4*dp[i-2];for(int j=3;j<=i;j++)if(j&1) dp[i]+=2*dp[i-j];else dp[i]+=3*dp[i-j];}int n,cas=1,ca;cin>>ca;while(ca--) {cin>>n;     cout<<cas++<<" "<<dp[n]<<endl;              }//system("PAUSE");return EXIT_SUCCESS;
}

这篇关于hdu 1992 Tiling a Grid With Dominoes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---