The mook jong 計數DP

　　　　　　　　　　　　The mook jong

ZJiaQ為了強身健體，決定通過木人樁練習武術。ZJiaQ希望把木人樁擺在自家的那個由1*1的地磚鋪成的1*n的院子里。由于ZJiaQ是個強迫癥，所以他要把一個木人樁正好擺在一個地磚上，由于木人樁手比較長，所以兩個木人樁之間地磚必須大于等于兩個，現在ZJiaQ想知道在至少擺放一個木人樁的情況下，有多少種擺法。

輸入描述

輸入有多組數據，每組數據第一行為一個整數n(1 < = n < = 60)

輸出描述

對于每組數據輸出一行表示擺放方案數

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 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;i<MS;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

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/273069.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/273069.shtml
英文地址，請注明出處：http://en.pswp.cn/news/273069.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！