The mook jong

Accepts: 506

Submissions: 1281

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

ZJiaQ为了强身健体，决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症，所以他要把一个木人桩正好摆
在一个地砖上，由于木人桩手比较长，所以两个木人桩之间地砖必须大于等于两个，现在ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。

输入描述

输入有多组数据，每组数据第一行为一个整数n(1 < = n < = 60)

输出描述

对于每组数据输出一行表示摆放方案数

输入样例

输出样例

1

2

3

5

8

12

题意：中文题面;

题解：递推处理   考虑当前位置pos能做出的最大贡献（前pos块砖按要求摆放木人桩 有dp[pos]种情况在pos位置摆放一个）;

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 long long dp[];

 int n;

 int main(){

     while(scanf("%d",&n)!=EOF){

         long long sum=;

         for(int i=;i<=n;i++) dp[i]=;

         for(int i=;i<=n;i++)

             for(int j=i-;j>=;j--) dp[i]+=dp[j];

         for(int i=;i<=n;i++) sum+=dp[i];

         printf("%lld\n",sum);

     }

 }

巴特西

HDU 5366 dp 递推

The mook jong

最新文章

热门文章