建站技术分享,可以注册的网站,国内十大网站建设品牌,汽贸公司网站建设The mook jong ZJiaQ为了强身健体#xff0c;决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症#xff0c;所以他要把一个木人桩正好摆在一个地砖上#xff0c;由于木人桩手比较长#xff0c;所以两个木人桩之间… The mook jong ZJiaQ为了强身健体决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症所以他要把一个木人桩正好摆在一个地砖上由于木人桩手比较长所以两个木人桩之间地砖必须大于等于两个现在ZJiaQ想知道在至少摆放一个木人桩的情况下有多少种摆法。 输入描述 输入有多组数据每组数据第一行为一个整数n(1 n 60) 输出描述 对于每组数据输出一行表示摆放方案数 1 #include iostream2 #include cstdio3 #include cstring4 #include cmath5 #include algorithm6 using namespace std;7 typedef long long LL;8 const int MS 62;9
10 //令f[i]为最后一个木人桩摆放在i位置的方案令s[i]为f[i]的前缀和。
11 //很容易就能想到f[i]s[i-3]1,s[i]s[i-1]f[i],而s[n]即是所求答案。
12 //本题唯一一个值得注意的点就是当n接近60时会爆int。
13
14 LL f[MS];
15 LL s[MS];
16
17 int main()
18 {
19 int n;
20 memset(f,0,sizeof(f));
21 memset(s,0,sizeof(s));
22 f[1] 1;
23 f[2] 1;
24 s[1] 1;
25 s[2] 2;
26 for(int i 3;iMS;i)
27 {
28 f[i] s[i-3] 1;
29 s[i] s[i - 1] f[i];
30 }
31 while(scanf(%d,n)!EOF)
32 {
33 printf(%d\n,s[n]);
34 }
35 return 0;
36 } 转载于:https://www.cnblogs.com/hutaishi/p/4713979.html
