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)

输出描写叙述

对于每组数据输出一行表示摆放方案数

输入例子

输出例子

这个题目有一个递推关系就是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 递推

The mook jong

最新文章

热门文章