## Friday, December 2, 2016

### HDU 5366 - The mook jong

http://acm.hdu.edu.cn/showproblem.php?pid=5366

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 mook jong， the distance of two mook jongs should be equal or more than 2 bricks. Now ZJiaQ want to know how many ways can ZJiaQ put mook jongs legally(at least one mook jong).
Input
There ar multiply cases. For each case, there is a single integer n( 1 < = n < = 60)
Output
Print the ways in a single line for each case.
Sample Input
```
1
2
3
4
5
6
```
Sample Output
```
1
2
3
5
8
12
```
http://www.lai18.com/content/4329060.html

http://www.cnblogs.com/fenice/p/5321679.html

### 方法一：

区间dp。
dp[i][j]表示前i个地砖放j个木人桩(其中第i个地砖肯定有放东西，要不然就不会是dp[i][j]，而是dp[k][j](k<i) )
则易得转移方程 dp[i][j]=sum(dp[k][j-1]),其中k<i-2;
初始化要注意：dp[i][1]=1,而其他则都清零。

http://blog.csdn.net/david_jett/article/details/47376251
```  状态转移方程： dp[i]=dp[i-1]+dp[i-3]+1。
dp[i]的含义是到i这个位置为止，有多少种方案数，也就是答案。因为dp表示的是合法的解，所以之前一定已经至少放了一个木桩了。dp[i-1]代表的是当前位置i不放木桩，
dp[i-3]代表的是当前位置放，因为间隔为2，所以不论前面第三个位置有没有，当前位置i都可以放置1个木桩，至于最后加上的一个1，开始没怎么理解，其实它代表的是前面i-1

1. long long dp[65]={0,1,2,3};
2. void init()
3. {
4.   for(int i=4;i<=60;i++)
5.       dp[i]=dp[i-1]+dp[i-3]+1;
6. }
7. int main()
8. {
9.     init();
10.     int n;
11.     while(~scanf("%d",&n))
12.     {
13.         printf("%lld\n",dp[n]);
14.     }
15.     return 0;
16. }
http://www.it610.com/article/5474922.htm

`int` `main()`
`{`
`    ``int` `n,i;`
`    ``long` `long` `s[70],f[70];``//s[i]表示i个木桩时的结果，f[i]表示把最后一个木桩放到第i个位置的方案数`
`    ``while``(cin>>n)`
`    ``{`
`        ``s[1]=1;`
`        ``s[2]=2;`
`        ``s[3]=3;`
`        ``f[1]=f[2]=f[3]=1;`
`        ``for``(i=4;i<=n;i++)`
`        ``{`
`            ``f[i]=s[i-3]+1;`
`            ``s[i]=s[i-1]+f[i];`
`        ``}`
`        ``cout<<s[n]<<endl;`
`    ``}`

`    ``return` `0;`
`}`