# The mook jong 计数DP

```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 }```

## HDU - 5366 The mook jong (dp动态规划)

The mook jong Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 62    Accepted Submission(s): 40 Problem Description ![](../../data/images/C613-1001-1.jpg) ZJiaQ want to become a strong man, so h

## The mook jong

ZJiaQ want to become a strong man, so he decided to play the mook jong.ZJiaQ want to put some mook jongs in his backyard. His backyard consist of n bricks that is 1*1,so it is 1*n.ZJiaQ want to put a mook jong in a brick. because of the hands of the

## HDU4901 The Romantic Hero 计数DP

2014多校4的1005 题目:http://acm.hdu.edu.cn/showproblem.php?pid=4901 The Romantic Hero Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 393    Accepted Submission(s): 150 Problem Description There i

## CodeForces 176B Word Cut （计数DP）

Word Cut Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 176B Description Let's consider one interesting word game. In this game you should transform one word into another through specia