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
在1*n的院子里铺有1*1的地板，在地板上里放置木人桩，木人桩之间至少相隔2快地板，问至少放置一个木人桩的情况下，可能的情况

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
个位置都没放置木桩，而在当前位置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

令f[i]为最后一个木人桩摆放在i位置的方案，令s[i]为f[i]的前缀和，即s[i]=f[0]+f[1]+...+f[i]。很容易就能想到f[i]=s[i-3]+1，因为最后一个木人放到最后一个位置，因此只有i-3个木人是可用的，再加上最后一种情况，s[i]=s[i-1]+f[i],而s[n]即是所求答案。本题唯一一个值得注意的点就是当n接近60时会爆int。

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;

}