首页 > 代码库 > hdu2606（递推）
hdu2606（递推）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2606
题意: 用1*1，2*2，3*3，4*4的正方形填充4*n的矩形, 问有多少种不同填法。
分析： f[i] = f[i - 1] + f[i - 2] * 4 + f[i - 3] * 2 + f[i - 4] * 1 + 对错位的情况(即2*(f[n-3] + f[n-4] + ...f[0]), f[0]初始化为1)
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 19890907#define inf 0x3f3f3f3f#define N 10010using namespace std;int f[110];void init(){ f[0]=1;f[1]=1;f[2]=5;f[3]=13; for(int i=4;i<=100;i++) { f[i]=(f[i-4]+f[i-3]*2+f[i-2]*4+f[i-1])%mod; for(int j=3;j<=i;j++)f[i]=(f[i]+2*f[i-j])%mod; }}int main(){ int n,t; init(); scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d\n",f[n]); }}
hdu2606（递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。