noip2001 數的計算 （動态規劃）

A1130. 數的計算

1.0s   記憶體限制：

256.0MB  

​​381​​   AC次數：

254   平均分：

72.34

将本題分享到：

​​檢視未格式化的試題​​​   

​​​送出​​​   

​​​試題讨論​​

試題來源

　　NOIP2001 普及組

問題描述

　　我們要求找出具有下列性質數的個數(包含輸入的自然數n):

　　先輸入一個自然數n(n<=1000),然後對此自然數按照如下方法進行處理:

　　1. 不作任何處理;

　　2. 在它的左邊加上一個自然數,但該自然數不能超過原數的一半;

　　3. 加上數後,繼續按此規則進行處理,直到不能再加自然數為止.

輸入格式

　　一個數n

輸出格式

　　一個數表示答案

樣例輸入

6

樣例輸出

6

樣例說明

　　滿足條件的數為6,16,26,126,36,136

解析：設b[i]表示輸入數字為 i 時的答案，a[i]=b[1]+...+b[i]，則有如下關系：

           a[i]=a[i-1]+b[i]

           b[i]=a[i/2]+1(這裡加的 1 是單獨一個數字 i 的情況)

           ==>a[i]=a[i-1]+a[i/2]+1

           那麼當輸入數字為 n 時，答案即為a[n/2]+1；

代碼：

#include<cstdio>

const int maxn=500;
int a[maxn+20];

int main()
{
  int i,j,n;
  scanf("%d",&n);
  a[1]=1,j=n/2;
  for(i=2;i<=j;i++)a[i]=a[i-1]+a[i/2]+1;
  printf("%d\n",a[j]+1);
  return 0;
}