p1057 数的计算

川长思鸟来 2022-07-11 09:22 189阅读 0赞

数的计数  
描述 Description  
我们要求找出具有下列性质数的个数(包含输入的自然数n):  
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:  
1.不作任何处理;  
2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;  
3.加上数后,继续按此规则进行处理,直到不能再加自然数为止.  
输入格式 Input Format  
一行一个整数  
输出格式 Output Format  
一个数即满足条件的个数  
样例输入 Sample Input

6  
样例输出 Sample Output

时间限制 Time Limitation  
各个测试点1s  
注释 Hint  
满足条件的数为 6 (此部分不必输出)  
　　　　　　 16  
　　　　　　 26  
　　　　　　 126  
　　　　　　 36  
　　　　　　 136  
来源 Source  
Noip2001普及组第1题

如果直接暴力模拟的话，很容易超时。  
所以找一找有没有什么关系。

<table> 
 <thead> 
  <tr> 
   <th>n</th> 
   <th align="right">h(n)</th> 
   <th align="center">满足条件的数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td align="right">1</td> 
   <td align="center">1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td align="right">2</td> 
   <td align="center">2,12</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td align="right">2</td> 
   <td align="center">3,13</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td align="right">4</td> 
   <td align="center">4,14,24,124</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td align="right">4</td> 
   <td align="center">5,15,25,125</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td align="right">6</td> 
   <td align="center">6,16,26,36,126,126</td> 
  </tr> 
  <tr> 
   <td>..</td> 
   <td align="right">…</td> 
   <td align="center">..</td> 
  </tr> 
 </tbody> 
</table>

当n=i时，满足数量的数有1,1i,12i…  
对于第i个数，如果它是奇数，那么h(i)=h(i-1)；如果它是偶数，那么h(i)=h(i-1)+h(\[i/2\])

#include<iostream>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin>>n;
        int f[1001]={
       0};
        f[1]=1;
        for (int i=2;i<=n;++i)
        {
            if (i%2==0) f[i]=f[i-1]+f[i/2];
            else f[i]=f[i-1];
        }
        cout<<f[n];
    }