蓝桥

【问题描述】

小明想知道，满足以下条件的正整数序列的数量：
1. 第一项为 n；
2. 第二项不超过 n；
3. 从第三项开始，每一项小于前两项的差的绝对值。
请计算，对于给定的 n，有多少种满足条件的序列。

【输入格式】

输入一行包含一个整数 n。

【输出格式】

输出一个整数，表示答案。答案可能很大，请输出答案除以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。

num(pre,cur) = num(cur,1) + num(cur,2) + ... +num(cur,abs(pre-cur)-1) + 1
pre表示前一个数，cur代表当前的数，选定之后，序列种数等于以cur为前序，以1到abs-1为当前的序列数的总和再加1.
如num(5,2) = num(2,1)+num(2,2).

优化一：

如果我们用num(i,j)表示前一个数是i，当前数是j的合法序列的个数；

比如求num(5,4)，差为5-4=1，故它的结果等于num(3,4)

因此num(5,4)=num(3,4)，求num(5,4)的时候可以先看num(3,4)求出来没，求num(3,4)的时候也可以先看num(5,4)求出来没。

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 const int INF=0x3f3f3f3f; const LL INFF=0x3f3f3f3f3f3f3f3f;
 4 const double eps =1e-8;
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 using namespace std;
 8 
 9 int G[1005][1005];//记录状态 
10 int n;
11 int ans;
12 
13 void DFS(int fa, int u)
14 {
15     if(G[fa][u]!=-1) return ;
16     int cha=abs(fa-u);
17     if(fa>u&&u-cha>0&&G[u-cha][u]!=-1)
18     {
19         G[fa][u]=G[u-cha][u];
20         return ;
21     }
22     else if(fa<u&&u+cha<=n&&G[u+cha][u]!=-1)
23     {
24         G[fa][u]=G[u+cha][u];
25         return ;
26     }
27     G[fa][u]=1;
28     for(int i=cha-1;i>=1;i--)
29     {
30         DFS(u,i);
31         G[fa][u]=(G[fa][u]+G[u][i])%10000;
32     }
33     return ;
34 }
35 
36 int main()
37 {
38     #ifdef DEBUG
39     freopen("sample.txt","r",stdin);
40     #endif
41     
42     scanf("%d",&n);
43     memset(G,-1,sizeof(G));
44     ans=0;
45     for(int i=n;i>=1;i--)
46     {
47         DFS(n,i);
48         ans=(ans+G[n][i])%10000;
49     }
50     printf("%d
",ans%10000);
51     
52     return 0;
53 }

优化二：

如果我们用nun(i,j)表示前一个数是i，当前数是1到j的合法序列的总个数；有num(i,j) = 1 + num(i,j-1) + num(j,abs(i-j)-1)

即分为两个部分：

（1）i作为前一个数，从1到j-1为当前数的合法序列的个数已经计算好

（2）求以j为尾数，后面选择1到abs(i-j)-1的合法序列的个数。

如 num(10,5)=num(10,4)+num(5,4);而不是枚举1到5；这样每次解答树只展开两个节点，相当于减少一层循环，虽然解答树的层次还是很深，但是由于记忆的存在，解空间仍然是N的平方。可在100ms内解决。

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 const int INF=0x3f3f3f3f;
 4 const double eps =1e-8;
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 using namespace std;
 8 
 9 int G[1005][1005];//记录状态,用G(i,j)表示前一个数是i，当前数是1到j的合法序列的总个数
10 
11 int DFS(int fa, int u)
12 {
13     if(u<=0) return 0;
14     if(G[fa][u]!=-1) return G[fa][u];
15     return G[fa][u]=(1+DFS(fa,u-1)+DFS(u,abs(fa-u)-1))%10000;
16 }
17 
18 int main()
19 {
20     #ifdef DEBUG
21     freopen("sample.txt","r",stdin);
22     #endif
23     
24     int n;
25     scanf("%d",&n);
26     memset(G,-1,sizeof(G));
27     printf("%d
",DFS(n,n)%10000);
28     
29     return 0;
30 }