编程笔记|蓝桥杯模拟赛收获（第9题）
本文非原创，主要是个人的学习笔记，参考链接：
2020年蓝桥杯模拟赛解题报告（CPP版本）
第九题
【问题描述】
小明想知道，满足以下条件的正整数序列的数量：
- 第一项为 n；
- 第二项不超过 n；
- 从第三项开始，每一项小于前两项的差的绝对值。
请计算，对于给定的 n，有多少种满足条件的序列。
【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
【样例输入】
4
【样例输出】
7
代码(这是我自己的)
#include<iostream>
#include<cmath>
using namespace std;
int dizzy(int a,int b)
{
unsigned int sum=1;
if(abs(a-b)<=1)
return 1;
else
for(int i=1;i<abs(a-b);i++)
sum=sum+dizzy(b,i);
return sum;
}
int main()
{
int n;
cin>>n;
unsigned int sum=0;
for(int i=1;i<=n;i++)
{
sum=sum+dizzy(n,i);
}
cout<<sum%10000;
}
(当时编出来还挺骄傲的，结果就拿了一点分，可能一点分都没拿。。。。)
这个题目的样例说明：
【样例说明】
以下是满足条件的序列：
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。
复杂度为（不太准确，反正就是指数级增大）所以这里对于最大评测数据基本上是算不出来，所以我的代码可能就拿了50分吧。蓝桥杯要求运行时间小于1s。这里解决办法是加入了记忆模式。
参考代码：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#define _for(i, x, y) for(register int i = x;i <= y;i++)
#define _fordw(i, x, y) for(register int i = x;i >= y;i--)
typedef long long LL;
using namespace std;
int N;
LL ans;
const int MOD = 10000;
//记忆数组默认初始值都是零
int mem[1001][1000];
//这个是主体递归算法
LL dfs(int pre, int cur) {
// 询问状态，如果有记忆直接调用
if (mem[pre][cur] != 0)
return mem[pre][cur];
LL ans = 1;
_for(j, 1,abs(pre-cur) - 1) {
ans = (ans + dfs(cur, j)) % MOD;
}
//记录状态
mem[pre][cur] = ans;
return ans;
}
void work() {
ans = 0;
cin >> N;
// f(pre,cur) = sum(f(cur,_new))|_new from 1 to abs(pre-cur)-1
_for(x, 1, N) ans = (ans + dfs(N, x)) % MOD;
cout << ans << endl;
}
分析：这个代码可以拿80分，n=1000。大概1000-2000ms的样子，超时也超的不多。记忆原理，我想到了查表法。。。哈哈。
文中的记录状态和询问状态都写得很清楚了。我反正是学到了flag。
这条代码的时间复杂度是,所以需要将算法继续优化。
优化代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
typedef long long LL;
using namespace std;
int N;
const int MOD = 10000;
int mem[1001][1000];
int dfs(int pre, int cur) {
if (cur <= 0) return 0;
if (mem[pre][cur] != 0) return mem[pre][cur];
return mem[pre][cur] = (1 + dfs(pre, cur - 1) + dfs(cur, abs(pre - cur) - 1)) % MOD;
}
void work() {
cin >> N;
cout << dfs(N, N) << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a = clock();
work();
int b = clock();
clog << (b - a) << endl;
return 0;
}
分析：
这段代码的mem数组和上一个不一样，上一个代表dfs(i,j)的结果。这里的mem（i,j）的意思是以i开头1~j的所有排序总和，如果你要计算4开头的所有满足这类要求的数组,那么就是mem（4,4），其实与第一种差不多，只是递归的方式不一样。
举例
- f(4,4)=f(4,3)+
f(4,-1)+1（4 4本身算一种) - f(4,3)=f(4,2)+
f(3,0)+1 (4 3本身算一种) - f(4,2)=f(4,1)+f(2,1)+1 (4 2 本身)
- f(2,1)=
f(2,0)+f(1,0)+1(简单来说就是 4 2 1)算一种 - f(4,1)=
f(4,0)+f(1,2)+1(4 1本身) - f(1,2)=f(1,1)+
f(2,0)+1(4 1 2本身) - f(1,1)=
f(1,0)+(1,-1)+1(4 1 1本身)
（划去的都等于0）
妙啊！终于把自己弄懂了
拓展
查表法，就是骗分的技巧。就是如果一道题结果是对的，但是超时的话，可以私下运行把数据范围内的所有结果都输出到一个数组里，那么提交的代码就是根据提供的数访问数组，这样时间复杂度是哈哈。拿着道题举例我们是将代码2，运行速度其实还可以，可以将代码2中的mem数组1000以内的结果全求出来，大概花个10秒左右，再把二维数组输出到cmd或文件里。然后用宏定义在程序里一个个赋值就行了，然后编个函数访问结果就行。为了分拼了！hhh
