最新消息:点击查看大S的省钱秘笈

Vijos P1130 数的计数 C语言版

Vijos题解 Slyar 36浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

描述 Description

我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理
l·不作任何处理:
2·在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3·加上数后,继续按此规则进行处理,直到不能再立生自然数为止。

Tip:一个奇怪的数列。。自己没研究出来,看的题解,估计把《组合数学》看了就明白了。。

1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60......s[i]=s[i div 2]+s[i-1]+1

我是用动态规划做的,虽然DFS也可以解决,不过DP最好。。。

#include <stdio.h>

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

转载请注明:Slyar Home » Vijos P1130 数的计数 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址