首页 > 代码库 > HDU 5366：The mook jong 递推

HDU 5366：The mook jong 递推

2024-09-22 19:39:24   212人阅读

The mook jong

 
 Accepts: 506
 
 Submissions: 1281
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
问题描写叙述
ZJiaQ为了强身健体。决定通过木人桩练习武术。
ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。
因为ZJiaQ是个强迫症，所以他要把一个木人桩正好摆在一个地砖上，因为木人桩手比較长。所以两个木人桩之间地砖必须大于等于两个，如今ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。
输入描写叙述
输入有多组数据。每组数据第一行为一个整数n(1 < = n < = 60)
输出描写叙述
对于每组数据输出一行表示摆放方案数
输入例子
1	
2
3
4
5
6
输出例子
1
2
3
5
8
12
这个题目有一个递推关系就是f[n]=f[n-1]+f[n-3]+1
怎么来的呢。就是当1*n-1个格子扩展到1*n的格子时，
当多出来的那一个格子为0时，数量=f[n-1]
当多出来的那一个格子为1时，数量=f[n-3]再加上新来的那个为1的格子，多了一种排法，即f[n-3]+1
事实上一个循环全然能够做，但当时着急对着这个公式写了一个递归，结果到五十几的时候出不来结果 ，太慢了，索性由于输入也不多就直接打表。。。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

int num;
long long a[65];

int main()
{
	a[1]=1;
	a[2]=2;
	a[3]=3;
	a[4]=5;
	a[5]=8;
	a[6]=12;
	a[7]=18;
	a[8]=27;
	a[9]=40;
	a[10]=59;
	a[11]=87;
	a[12]=128;
	a[13]=188;
	a[14]=276;
	a[15]=405;
	a[16]=594;
	a[17]=871;
	a[18]=1277;
	a[19]=1872;
	a[20]=2744;
	a[21]=4022;
	a[22]=5895;
	a[23]=8640;
	a[24]=12663;
	a[25]=18559;
	a[26]=27200;
	a[27]=39864;
	a[28]=58424;
	a[29]=85625;
	a[30]=125490;
	a[31]=183915;
	a[32]=269541;
	a[33]=395032;
	a[34]=578948;
	a[35]=848490;
	a[36]=1243523;
	a[37]=1822472;
	a[38]=2670963;
	a[39]=3914487;
	a[40]=5736960;
	a[41]=8407924;
	a[42]=12322412;
	a[43]=18059373;
	a[44]=26467298;
	a[45]=38789711;
	a[46]=56849085;
	a[47]=83316384;
	a[48]=122106096;
	a[49]=178955182;
	a[50]=262271567;
	a[51]=384377664;
	a[52]=563332847;
	a[53]=825604415;
	a[54]=1209982080;
	a[55]=a[54]+a[52]+1;
	a[56]=a[55]+a[53]+1;
	a[57]=a[56]+a[54]+1;
	a[58]=a[57]+a[55]+1;
	a[59]=a[58]+a[56]+1;
	a[60]=a[59]+a[57]+1;
	while(cin>>num)
	{
		cout<<a[num]<<endl;
	}

	return 0;
}





HDU 5366：The mook jong 递推


联系
我们