求符合条件的正整数序列的数量
本帖最后由 Given2001 于 2020-3-18 13:31 编辑问题描述：
小明想知道，满足以下条件的正整数序列的数量：
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都要算半天
有没有更好的办法，或者优化我的方法（本人萌新，代码写的烂大佬勿怪）
#include <iostream>
#include <cmath>
using namespace std;
int n;
int ret;
void ca(int a, int b)
{
int ab = abs(a - b);
int c;
for (c = 1; c < ab; c++)
{
ret++;
//cout << a << '\t' << b << '\t' << c << endl;
ca(b, c);
ret %= 10000;
}
}
int main()
{
cin >> n;
ret = 0;
for (int i = 1; i <= n; i++)
{
ret++;
//cout << n << '\t' << i << endl;
ca(n, i);
}
cout << ret << endl;
return 0;
}
研究了一晚上算是找到了点点规律，发出来大家共同学习=。=
（不一定对，有错误请大佬指正）
首先，我们先手算一下n为6时所有可能的序列（当然你也可以用代码）
6 1
6 1 1
6 1 2
6 1 3
6 1 3 1
6 1 3 1 1
6 1 4
6 1 4 1
6 1 4 1 1
6 1 4 1 2
6 1 4 2
6 1 4 2 1
6 2
6 2 1
6 2 2
6 2 3
6 3
6 3 1
6 3 1 1
6 3 2
6 4
6 4 1
6 4 1 1
6 4 1 2
6 5
6 6
我们可以发现：
当 4 1 的后面分支都是相同的（我也表达不明白，看图）
可以得出：
当前一个数(a)和后一个数(b)相同时，产生的结果数也是相同的
于是我们将结果数保存在一个二维数组中，下一次要用时直接取用
经过测试，有效的减少了运算量，对于n=1000也能1s内得出结果
（虽然我也不知道答案是否准确就对了，希望有做出不同思路的大佬能跟我校对下答案）
贴下我优化后的代码
#include <iostream>
#include <cmath>
//#include <ctime>
using namespace std;
int buff;
//clock_t clSt, clEd;
int ca(int a, int b)
{
if (buff != 0) {
//由于ab相同后续的可能性也相同，这里我直接取用之前保存的结果数
return buff;
}
int ab = abs(a - b);
int c;
int count = 1;
for (c = 1; c < ab; c++)
{
//cout << a << '\t' << b << '\t' << c << endl;
count += ca(b, c);
}
count %= 10000;//每次都对结果取余，防止溢出（可能。。。还是会溢出）
buff = count;//保存结果
return count;
}
int main()
{
int n;
cin >> n;
//初始化
//clSt = clock();
int ret = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
buff = 0;
}
}
//第二个数
for (int i = 1; i <= n; i++)
{
//cout << n << '\t' << i << endl;
ret += ca(n, i);
}
ret %= 10000;
//clEd = clock();
cout << ret << endl;
//double runtime = (double)(clEd - clSt) / CLOCKS_PER_SEC;
//cout << "用时：" << runtime << endl;
return 0;
}
本帖最后由 Given2001 于 2020-3-29 13:19 编辑
2020年3月29日12:50:34 我又回来了{:10_266:}
竞赛老师已经讲解了这道题，看到老师的代码，我……
话不多说，先上代码
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;
int N;
const int MOD = 10000;
int mem;
int dfs(int pre, int cur) {
if (cur <= 0) return 0;
if (mem != 0) return mem;
return mem =
(1 + dfs(pre, cur - 1) + dfs(cur, abs(pre - cur) - 1)) % MOD;
}
void work() {
cin >> N;
cout << dfs(N, N) << endl;
}
int main() {
int a = clock();
work();
int b = clock();
clog << (b - a) << "ms" << endl;
return 0;
}
思路就是在我之前的优化代码上进一步优化。
原本递归函数中研究的是a与b所得出的结果数目
也就是说再最极端的情况下（记忆数组被填满）
我们需要运算结果1000*1000次，
再加上main函数里的一层循环
就是1000*1000*1000次，这时候我们就要考虑把最外层的循环给去掉
也就是把递归研究的问题转换为a与1~b所得出的结果总数
这样即使记忆数组被填满，也只有1000*1000次计算
大概是这样……
测试结果
14ms解决战斗！！
平均12ms就可以
原文地址 也不会 坐等大神回复 一点都不萌新{:10_266:} 冒个泡 跟大佬学习一下 大佬，敬仰 大佬 没有大佬来验证下我的思路吗。。。{:5_107:} 墨羽岚 发表于 2020-3-16 17:13
一点都不萌新
{:10_254:}我是货真价实的萌新啊，大佬可能根本不会考虑枚举把{:10_266:}不懂大佬的世界 完全看不懂，等大神指教 枚举法行不。。。虽然很麻烦 乔珂珂 发表于 2020-3-27 11:37
枚举法行不。。。虽然很麻烦
我一开始的方法就是枚举啊，emmm你指的枚举是啥{:10_277:} 为什么数学界的小明也跑到编程界来了{:10_266:}
纯属冒个泡，但这道题还真不会{:10_266:} 烟肖雨晨 发表于 2020-3-27 14:53
为什么数学界的小明也跑到编程界来了
纯属冒个泡，但这道题还真不会
小明是个神秘的人物{:10_334:} 谢谢谢谢 一点都不萌新{:5_100:} 学习一下~
~~ 墨羽岚 发表于 2020-3-16 17:13
一点都不萌新
老师的标准答案出来了，有兴趣看看嘛
页:
[1]
2