。

先输入一个自然数n(n≤1000)#xff0c;然后对此自然数按照如下方法进行处理#xff1a;不作任何处理#xff1b;在它的左边加上一…1316【例4.6】数的计数(Noip2001)

【题目描述】

。

先输入一个自然数n(n≤1000)然后对此自然数按照如下方法进行处理不作任何处理在它的左边加上一个自然数但该自然数不能超过原数的一半加上数后继续按此规则进行处理直到不能再加自然数为止。

【输入】

一个自然数左边加上一个自然数举例-100左边加上后可以为5010025504910024100所以他的数量为1~50这五十个自然数的每次计数之和由于每个自然数独一无二左边加上一个自然数就多了该自然数的排列方式所以可以理解为前n/2个自然数不同排列组成的数的个数之和由于数据庞大在使用递归式时可以考虑该数组的值是否已经求了如果已求则可以直接跳过节省运行时间记忆搜索如果采用一层for循环的递归方式则会超时用一个变量去存由于每次都要从1开始计算所以会超时

#includebits/stdc.h

//由于直接每次num(i)只是用sum记忆次数则会超时所以选择用记忆的方式每次计算后存起来

int

i1;im/2;i){num(i);//每次都递归一下(避免前面的数未计数)

a[m]a[i];}