欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[题记]序列计数-蓝桥杯

程序员文章站 2022-09-04 21:07:28
题目:序列计数 【问题描述】小明想知道,满足以下条件的正整数序列的数量:1. 第一项为 n;2. 第二项不超过 n;3. 从第三项开始,每一项小于前两项的差的绝对值。请计算,对于给定的 n,有多少种满足条件的序列。 【输入格式】输入一行包含一个整数 n。【输出格式】输出一个整数,表示答案。答案可能很 ......

题目:序列计数

【问题描述】
小明想知道,满足以下条件的正整数序列的数量:
1. 第一项为 n;
2. 第二项不超过 n;
3. 从第三项开始,每一项小于前两项的差的绝对值。
请计算,对于给定的 n,有多少种满足条件的序列。


【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一个整数,表示答案。答案可能很大,请输出答案除以10000的余数。


【样例输入】
4
【样例输出】
7
【样例说明】
以下是满足条件的序列:
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
【评测用例规模与约定】
对于 20% 的评测用例,1 <= n <= 5;
对于 50% 的评测用例,1 <= n <= 10;
对于 80% 的评测用例,1 <= n <= 100;
对于所有评测用例,1 <= n <= 1000。


思路:记忆化递归

从题目第三点可以得出递归公式:

  f(old,now)的意思是一old为之前的元素,now为当前的元素的序列总和。

  f(old,now) = f(now, 1) + .... + f(now,|old-now|-1) + 1;

  

  由此我们根据2,3条件得出:f(old,now)的序列总和 = 1 + f( old, now -1 ) + f( now, | old - now | - 1 );

 

由此得出代码(c):

  

#include <stdio.h>
#include <math.h>
int hx[1001][1001] = {0};

long long int dfs( int old, int now ) {
if( now <= 0 ) return 0; if( hx[old][now] != 0 ) return hx[old][now]; // 从第三项开始每一项小于前两项的差的绝对值,即从1到fabs(old-now)-1 // 以old和now开头的序列,总共有:自己+ now < old的+ 第三项开始符合条件的 hx[old][now] = ( 1+dfs(old,now-1)+dfs(now,fabs(old-now)-1) )%10000; return hx[old][now]; } int main(){ int num; scanf("%d",&num); printf("%i64d",dfs(num,num)); return 0; } //从第三项开始,符合递归式: //f(old,now) = f(now, 1) + .... + f(now,|old-now|-1) + 1; // ★从1到old和now的绝对值-1 在加上自己

 

2020-03-25-20:57:01