hdu 1143 技巧

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

n 为奇数 0
n为偶数, dp[2]=3;
令dp[0]=1; dp[1]=0; dp[3]=0;

递推发现：其实我并没有发现，都是人家发现的 汗……
如果最后两列拼满 则为dp[n-2]*dp[2]=dp[n-2]*3;
如果最后两列拼不满一定是最后四列拼满的，两列拼不满有2中拼法

我看不懂啊， 不说了，反正最后就是得到一个通项公式
dp[i]=4*dp[i-2]-dp[i-4];

参考博客：
http://blog.csdn.net/liwen_7/article/details/7998930

http://www.cnblogs.com/slgkaifa/p/7093245.html

AC 代码

#include <iostream>
#include<cstdio>
using namespace std;int main()
{int n;int dp[31];//dp[0]=1;// dp[1]=0;  // if i%2==1  0// dp[2]=3;dp[0]=1;dp[1]=0;dp[2]=3;dp[3]=0;for(int i=4;i<31;i++){dp[i]=4*dp[i-2]-dp[i-4];}int ans=0;while(scanf("%d",&n)){if(n==-1) break;printf("%d\n",dp[n]);}return 0;
}

这篇关于hdu 1143 技巧的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---