題目：序列計數
【問題描述】
小明想知道，滿足以下條件的正整數序列的數量：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40814.html
標籤：C
下一篇：使用mutex同步多行程