求符合条件的正整数序列的数量

Given2001

问题描述：

　　小明想知道，满足以下条件的正整数序列的数量：

　　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。

我的疑问
以下是我的代码，纯粹通过递归暴力算的，问题就是数据一大，甚至n超过15都要算半天
有没有更好的办法，或者优化我的方法（本人萌新，代码写的烂大佬勿怪）

1. 
   
2. #include <iostream>
   
3. #include <cmath>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int n;
   
8. int ret;
   
9. void ca(int a, int b)
   
10. {
    
11.     int ab = abs(a - b);
    
12.     int c;
    
13.     for (c = 1; c < ab; c++)
    
14.     {
    
15.         ret++;
    
16.         //cout << a << '\t' << b << '\t' << c << endl;
    
17.         ca(b, c);
    
18.         ret %= 10000;
    
19.     }
    
20. }
    
21. int main()
    
22. {
    
23.     cin >> n;
    
24.     ret = 0;
    
25.     for (int i = 1; i <= n; i++)
    
26.     {
    
27.         ret++;
    
28.         //cout << n << '\t' << i << endl;
    
29.         ca(n, i);
    
30.     }
    
31.     cout << ret << endl;
    
32.     return 0;
    
33. }
    

复制代码

Given2001

研究了一晚上算是找到了点点规律，发出来大家共同学习=。=
（不一定对，有错误请大佬指正）
首先，我们先手算一下n为6时所有可能的序列（当然你也可以用代码）

1. 
   
2. 6       1
   
3. 6       1       1
   
4. 6       1       2
   
5. 6       1       3
   
6. 6       1       3       1
   
7. 6       1       3       1       1
   
8. 6       1       4
   
9. 6       1       4       1
   
10. 6       1       4       1       1
    
11. 6       1       4       1       2
    
12. 6       1       4       2
    
13. 6       1       4       2       1
    
14. 6       2
    
15. 6       2       1
    
16. 6       2       2
    
17. 6       2       3
    
18. 6       3
    
19. 6       3       1
    
20. 6       3       1       1
    
21. 6       3       2
    
22. 6       4
    
23. 6       4       1
    
24. 6       4       1       1
    
25. 6       4       1       2
    
26. 6       5
    
27. 6       6
    

复制代码

我们可以发现：
当 4 1 的后面分支都是相同的（我也表达不明白，看图）
可以得出：
当前一个数(a)和后一个数(b)相同时，产生的结果数也是相同的
于是我们将结果数保存在一个二维数组中，下一次要用时直接取用
经过测试，有效的减少了运算量，对于n=1000也能1s内得出结果
（虽然我也不知道答案是否准确就对了，希望有做出不同思路的大佬能跟我校对下答案）
贴下我优化后的代码

1. #include <iostream>
   
2. #include <cmath>
   
3. //#include <ctime>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int buff[1001][1001];
   
8. //clock_t clSt, clEd;
   
9. 
   
10. int ca(int a, int b)
    
11. {
    
12.     if (buff[a][b] != 0) {
    
13.         //由于ab相同后续的可能性也相同，这里我直接取用之前保存的结果数
    
14.         return buff[a][b];
    
15.     }
    
16.     int ab = abs(a - b);
    
17.     int c;
    
18.     int count = 1;
    
19.     for (c = 1; c < ab; c++)
    
20.     {
    
21.         //cout << a << '\t' << b << '\t' << c << endl;
    
22.         count += ca(b, c);
    
23.     }
    
24.     count %= 10000;//每次都对结果取余，防止溢出（可能。。。还是会溢出）
    
25.     buff[a][b] = count;//保存结果
    
26.     return count;
    
27. }
    
28. int main()
    
29. {
    
30.     int n;
    
31.     cin >> n;
    
32.     //初始化
    
33.     //clSt = clock();
    
34.     int ret = 0;
    
35.     for (int i = 0; i < n; i++)
    
36.     {
    
37.         for (int j = 0; j < n; j++)
    
38.         {
    
39.             buff[i][j] = 0;
    
40.         }
    
41.     }
    
42.     //第二个数
    
43.     for (int i = 1; i <= n; i++)
    
44.     {
    
45.         //cout << n << '\t' << i << endl;
    
46.         ret += ca(n, i);
    
47.     }
    
48.     ret %= 10000;
    
49.     //clEd = clock();
    
50.     cout << ret << endl;
    
51.     //double runtime = (double)(clEd - clSt) / CLOCKS_PER_SEC;
    
52.     //cout << "用时：" << runtime << endl;
    
53.     return 0;
    
54. }

复制代码

Given2001

2020年3月29日12:50:34 我又回来了
竞赛老师已经讲解了这道题，看到老师的代码，我……

话不多说，先上代码

1. #include <cstdlib>
   
2. #include <cstring>
   
3. #include <ctime>
   
4. #include <iostream>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int N;
   
9. const int MOD = 10000;
   
10. int mem[1001][1000];
    
11. 
    
12. int dfs(int pre, int cur) {
    
13.     if (cur <= 0) return 0;
    
14.     if (mem[pre][cur] != 0) return mem[pre][cur];
    
15.     return mem[pre][cur] =
    
16.                (1 + dfs(pre, cur - 1) + dfs(cur, abs(pre - cur) - 1)) % MOD;
    
17. }
    
18. 
    
19. void work() {
    
20.     cin >> N;
    
21.     cout << dfs(N, N) << endl;
    
22. }
    
23. 
    
24. int main() {
    
25.     int a = clock();
    
26.     work();
    
27.     int b = clock();
    
28.     clog << (b - a) << "ms" << endl;
    
29.     return 0;
    
30. }

复制代码

思路就是在我之前的优化代码上进一步优化。
原本递归函数中研究的是a与b所得出的结果数目
也就是说再最极端的情况下（记忆数组被填满）
我们需要运算结果1000*1000次，
再加上main函数里的一层循环
就是1000*1000*1000次，这时候我们就要考虑把最外层的循环给去掉
也就是把递归研究的问题转换为a与1~b所得出的结果总数
这样即使记忆数组被填满，也只有1000*1000次计算
大概是这样……

测试结果
14ms解决战斗！！
平均12ms就可以
原文地址

winsome8538

也不会 坐等大神回复

墨羽岚

一点都不萌新

V流年V

冒个泡

珂乔乔

跟大佬学习一下

如果孤独感

大佬，敬仰

如果孤独感

大佬

Given2001

没有大佬来验证下我的思路吗。。。

Given2001

墨羽岚 发表于 2020-3-16 17:13
一点都不萌新

我是货真价实的萌新啊，大佬可能根本不会考虑枚举把不懂大佬的世界

依可儿

完全看不懂，等大神指教

乔珂珂

枚举法行不。。。虽然很麻烦

Given2001

乔珂珂 发表于 2020-3-27 11:37
枚举法行不。。。虽然很麻烦

我一开始的方法就是枚举啊，emmm你指的枚举是啥

烟肖雨晨

为什么数学界的小明也跑到编程界来了
纯属冒个泡，但这道题还真不会

Given2001

烟肖雨晨 发表于 2020-3-27 14:53
为什么数学界的小明也跑到编程界来了
纯属冒个泡，但这道题还真不会

小明是个神秘的人物

wuhao4221961

谢谢谢谢

bailean

一点都不萌新

乔珂珂

学习一下~
~~

Given2001

墨羽岚 发表于 2020-3-16 17:13
一点都不萌新

老师的标准答案出来了，有兴趣看看嘛