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


题目:序列计数

【问题描述】
小明想知道,满足以下条件的正整数序列的数量:
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

 

  

 


作者:橙橙橙澄xs,发布于:2020/03/26
原文:https://www.cnblogs.com/Sxccz/p/LanQiao_9.html