NOIP_2001.PJ1:数的计数 解题报告

刚看到题目被吓到了，下面有一个Hit（提示），说用高精度，高精度我以前写过一次，几乎忘干净了……后来琢磨了好久，发现能够使用动态规划，注意观察一下样例，输入是6，共有：
6
16
26
126
36
136
设f[i]是以自然数i在最左边的个数，那么很容易发现方程f[i] = f[1] + f[2] + f[3] + …. + f[i/2] + 1;于是就产生了下面的代码：

C语言:

#include <stdio.h>
unsigned f[1001];

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

有更好的算法的高手请留个言，我在不断学习中。。