跳至正文

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

  • OI路程

刚看到题目被吓到了,下面有一个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;
}

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

发表回复

您的电子邮箱地址不会被公开。