本文主要是介绍HLJUOJ1128 HDU2046(数学递推),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1128: 递推求解专题练习三
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 8 Solved: 6
[ Submit][ Status][ Web Board]
Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数。
例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:
Input
输入数据只包含n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。
Output
对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。
Sample Input
1
3
2
Sample Output
1
3
2
HINT
注意数据范围室友有溢出,本oj建议用long long和%lld。
解题思路:
看来我的数学递推还是有救的。对于每个2*n的图案,我们都是用1*2或者2*1的方格去填充。f [ 0 ] = 1 , f [ 1 ] = 1,这是很明显的。 当图案为2*1时,只能用2*1的小图形填充。于是我开始乱搞,推出公式f [ i ] = f [ i - 1] + f[ i - 2 ];
最后说一下输出问题,如果在HDU上提交,那么要用I64d输出!!!
完整代码:
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")
typedef __int64 LL;
//typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
const int maxn = 55;
LL f[maxn];
int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endiff[0] = 1;f[1] = 1;f[2] = 2;for(int i = 3 ; i < maxn; i ++){f[i] = f[i - 1] + f[i - 2];}int n;while(~scanf("%d",&n)){printf("%I64d\n",f[n]);}
}
这篇关于HLJUOJ1128 HDU2046(数学递推)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!