acm递推求解

acm递推求解

不管道路多么崎岖坎坷，我永远不停下追逐梦想的脚步！

商人，不佩剑；

超级楼梯

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 0 Accepted Submission(s) : 0 Problem Description

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input 2 2 3

Sample Output 1 2

Author lcy

Source

2005实验班短学期考试 我的错误代码

#include<stdio.h> int main()

{

int n,i,j,M; int count=0;

while(scanf("%d",&n)!=EOF) {

scanf("%d",&M);

while(n--){

for(i=0;i<=M;i++) {

for(j=0;j<=(int)(M/2);j++) {

if(i+2*j==M)count++; } } }

printf("%d\\n",count); count=0; }

return 0;

}当你到达第n阶的时候有两种到达方式。 在n-1处上 1个楼梯。在n-2处上2个楼梯。。

所以上N阶楼梯的情况总数=上n-1的总数+上n-2的总数 这样递推公式就出来了。。 f（n）=f（n-1）+f（n-2）

11111111111

#include<stdio.h> int s[41]; int main() { int t,n;

scanf("%d",&t);

s[1] = s[2] = 1; //第一级到第二级只一种，就在第一级当然只一种。 for(int i = 3;i < 41;i++) s[i] = s[i-1] + s[i-2];

while(t-- && scanf("%d",&n)) printf("%d\\n",s[n]); return 0;

}

一只小蜜蜂...

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 5 Accepted Submission(s) : 2 Problem Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中，蜂房的结构如下所示。

Input

输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output

对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

Sample Input 2 1 2 3 6

Sample Output 13

Author lcy

Source

递推求解专题练习（For Beginner）

我的错误代码

#include<stdio.h>

int main() {

long s[50]; int a,b,n;

scanf("%d",&n); s[1]=1;s[2]=2;

while(n-- && scanf("%d",&a,&b)) { int i,j; i=b-a;

for(j=1;j<=i;j++)

{s[j] = s[j-1] + s[j-2]; }

printf("%d\\n",s[j]); }

return 0; } 参考

Fibnacci 数列 C语言程序 main() {

long fib[40] = {1,1}; int i;

for(i=2;i<40;i++) {

fib[i ] = fib[i-1]+fib[i-2]; }

for(i=0;i<40;i++) {

printf("F%d==%d\\n", i, fib[i ]); }

return 0; }

111111111111111111 #

include <stdio.h> int main(){

__int64 dp[50]; int i, z, a, b;

dp[1] = 1; dp[2] = 1; for (i=3; i<50; i++){ dp[i] = dp[i-2]+dp[i-1]; }

scanf("%d", &z); while (z-- != 0){

scanf("%d %d", &a, &b); printf("%I64d\\n", dp[b-a+1]); }

return 0; }

不容易系列之(3)—— LELE的RPG难题

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 3 Accepted Submission(s) : 0 Problem Description 人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即"可乐"）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题:

有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。

Output

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input 1 2

Sample Output 3 6

Author lcy

Source

递推求解专题练习（For Beginner） 我的错误代码

#include <stdio.h> int main() {

__int64 f[51]; int i,n;

f[1]=3;f[2]=6;f[3]=6;f[4]=36; for(i=5;i<51;i++) {

f[i]=2*f[i-1]; }

while(scanf("%d",&n)!=EOF) {

printf("%I64d\\n",f[n]); }

return 0; }

11111111111111

#include <stdio.h> int main() {

__int64 f[51]={3,6,6}; int i,n;

for(i=3;i<50;i++) {

f[i]=f[i-1]+2*f[i-2]; }

while(scanf("%d",&n)!=EOF) {

printf("%I64d\\n",f[n-1]); }

return 0; }

骨牌铺方格

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 16 Accepted Submission(s) : 6 Problem Description

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.

例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

Input

输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

Output

对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

Sample Input 132

Sample Output 132

Author lcy

Source

递推求解专题练习（For Beginner） 太好了 竟然正确了

11111111111

#include <stdio.h> int main() {

__int64 f[50]={1,2,3}; int i,n;

for(i=3;i<50;i++) {

f[i]=f[i-1]+f[i-2]; }

while(scanf("%d",&n)!=EOF) {

printf("%I64d\\n",f[n-1]); }

return 0; }

阿牛的EOF牛肉串 Time Limit

: 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 3 Accepted Submission(s) : 4 Problem Description

今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿牛、XC以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由"E" "O" "F"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,阿牛同时禁止在串中出现O相邻的情况，他认为，"OO"看起来就像发怒的眼睛，效果不好。 你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？

PS: 阿牛还有一个小秘密，就是准备把这个刻有 EOF的牛肉干，作为神秘礼物献

给杭电五十周年校庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的ACMer向阿牛表示感谢！

再次感谢！

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。

Output

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input 12

Sample Output 38

Author lcy

Source

递推求解专题练习（For Beginner）

太好了，期待！ 1111111

#include<stdio.h> int main() {

__int64 f[40]={3,8}; int i,n;

for(i=2;i<40;i++) {

f[i]=2*(f[i-1]+f[i-2]); }

while(scanf("%d",&n)!=EOF) {

printf("%I64d\\n",f[n-1]); }

return 0; }

神、上帝以及老天爷

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 4 Accepted Submission(s) : 3 Problem Description

HDU 2006'10 ACM contest的颁奖晚会隆重开始了！

为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：

首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中； 然后，待所有字条加入完毕，每人从箱中取一个字条；

最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”

大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！

我的神、上帝以及老天爷呀，怎么会这样呢？

不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？

不会算？难道你也想以悲剧结尾？！

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包

含一个整数n(1<n<=20),表示参加抽奖的人数。

Output

对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。

Sample Input 12

Sample Output 50.00%

Author lcy

Source

递推求解专题练习（For Beginner）

真是我的神

1111111111111111111 #include <stdio.h> int main() {

int z, n, i;

__int64 l, a, b, t;

scanf("%d", &z); while (z--){

scanf("%d", &n); l = 1;

for (i=n; i>1; i--) l *= i;//sum number a = 0; b = 1;

for (i=3; i<=n; i++){ t = (a+b)*(i-1); a = b;//a[2] b = t;//a[3]

}//f[n]=(n-1)*(f[n-1]+f[n-2]) if (n < 3) t = n-1;

printf("%.2lf%%\\n", (double)t*100/l);//格式 }

return 0; }

不容易系列之一

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 17 Accepted Submission(s) : 10 Problem Description

大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！ 做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。

话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把40个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。

不幸的是，这种小概率事件又发生了，而且就在我们身边：

事情是这样的——HDU有个网名叫做8006的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给n个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！

现在的问题是：请大家帮可怜的8006同学计算一下，一共有多少种可能的错误方式呢？

Input

输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1<n<=20），n表示8006的网友的人数。

Output

对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。

Sample Input 23

Sample Output 12

Author lcy

Source

ACM暑期集训队练习赛（九）

竟这样简单

11111111111111111111 #include <stdio.h> int main() {

int n, i;

__int64 a, b, t;

while(scanf("%d", &n)!=EOF) {

a = 0; b = 1;

for (i=3; i<=n; i++){ t = (a+b)*(i-1);

a = b; b = t; }

if (n < 3) t = n-1;

printf("%I64d%\\n", t); }

return 0; }

折线分割平面

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 3 Accepted Submission(s) : 2 Problem Description

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。

Output

对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

Sample Input 212

Sample Output 27

Author lcy

Source

递推求解专题练习（For Beginner） 蒙了

111111111

#include<stdio.h> int t(int n) { int c;

if(n==1)c=2;

else c=t(n-1)+4*n-3;//关键 return c; }

int main() {

int t(int n); int n,i,m;

scanf("%d",&n); for(i=0;i<n;i++) {

scanf("%d",&m); printf("%d\\n",t(m));

}

return 0; }

Children’s Queue

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 6 Accepted Submission(s) : 2 Problem Description

There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM

Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

Input

There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)

Output

For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.

Sample Input 123

Sample Output 124

Author

SmallBeer (CML)

Source

杭电ACM集训队训练赛（VIII）

望洋兴叹

11111111111111

#include <stdio.h> const int maxn=1000;

int m[1002][1000]={{0},{1,1},{1,1}}; int f[1002][1000]={{0},{1,0},{1,1}}; void add(int a[],int b[],int c[]) { int i;

for (i=0;i<=a[0];i++) c[i]=a[i]; if (b[0]>c[0]) c[0]=b[0];

for (i=1;i<=c[0];i++) { c[i]+=b[i]; if (c[i]>9) { c[i]-=10; c[i+1]++; } if (c[c[0]+1]>0) c[0]++; }

int main() {

int i,n; for (i=3;i<=maxn+1;i++) {

add(m[i-1],f[i-1],m[i]); add(f[i-1],m[i-2],f[i]); }

}

while (scanf("%d",&n)!=EOF) { for (i=m[n+1][0];i>0;i--) printf("%d",m[n+1][i]); printf("\\n"); }

return 0; }

思路如下：

一个长度n的队列可以看成一个n - 1的队列再追加的1个小孩，这个小孩只可能是：

a.男孩，任何n - 1的合法队列追加1个男孩必然是合法的，情况数为f[n - 1]；

b.女孩，在前n - 1的以女孩为末尾的队列后追加1位女孩也是合法的，我们可以转化为n - 2的队列中追加2位女孩；

一种情况是在n - 2的合法队列中追加2位女孩，情况数为f[n - 2]；

但我们注意到本题的难点，可能前n - 2位以女孩为末尾的不合法队列（即单纯以1位女孩结尾），也可以追加2位女孩成为合法队列，而这种n - 2不合法队列必然是由n - 4合法队列+1男孩+1女孩的结构，即情况数为f[n - 4]。

若感觉本题较难，可先查看文章：[ACM_HDU_2045]LELE的RPG难题，思路与本题类似，但较为简单。

得出递推公式如下：

f[n] = f[n - 1] + f[n - 2] + f[n - 4]还有需要注意的是本题中可能得出极大的数字，如当n为1000时，结果为：

12748494904808148294446671041721884239818005733501580815621713101333980596197474744336199742452912998225235910891798221541303838395943300189729514282623665199754795574309980870253213466656184865681666106508878970120168283707307150239748782319037

这种超大数完全不是C++提供的数值类型能够储存的，因此我们可以使用二维数组来模拟超大数运算，代码如下：

[cpp] view plaincopyprint? #include<stdio.h>

int main(){ int n;

int f[1001][101] = {0}; f[0][1] = 1; f[1][1] = 1; f[2][1] = 2; f[3][1] = 4;

for(int i = 4; i < 1001; ++i){ for(int j = 1; j < 101; ++j){

f[i][j] += f[i - 1][j] + f[i - 2][j] + f[i - 4][j]; //数组的每一位相加

f[i][j + 1] += f[i][j] / 10000; //超过4位的部分保存至数组下一位中 f[i][j] %= 10000; //每位数组只保存其中4位 } }

while(scanf("%d", &n) != EOF){ int k = 100;

while(!f[n][k--]); //排除前面为空的数组

printf("%d", f[n][k + 1]); //输出结果的前四位 for(; k > 0; --k){

printf("d", f[n][k]); //输出其余的所有四位数字，若数字小于四位，则前面用0填充 }

printf("\\n"); }

return 0; }

母牛的故事

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 36 Accepted Submission(s) : 21 Problem Description

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头

开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。

n=0表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第n年的时候母牛的数量。 每个输出占一行。

Sample Input 2450

Sample Output 246

Author lcy

我的错误代码

#include<stdio.h> int main() {

int n,i;

int a[55]={2,2,3,4}; for(i=4;i<55;i++) {

a[i]=a[i-3]*3; }

while(scanf("%d",&n)!=EOF&&n!=0) {

printf("%d\\n",a[n-1]); }

return 0; }

111111111111111 #include<stdio.h> int main() {

int n,s[100],i,sum;

while(scanf("%d",&n)!=EOF) {

if(n==0)break; s[0]=s[1]=s[2]=0;

s[3]=1;

for(i=1;i<n;i++) {

s[3]=s[3]+s[2];//a[i]=a[i-1]+a[i-2] s[2]=s[1]; s[1]=s[0]; s[0]=s[3]; }

sum=s[0]+s[1]+s[2]+s[3];

printf("%d\\n",sum); }

return 0; }

递推题，它们写出来的代码都很简单。但关键看你能不能找到规律。 本题中，第n年的牛的来源有2中:

第n-1年的牛

第n-3年的牛所生的小牛

而递推的出口是第1年为1头，第2年为2头，第3年为3头。

#include<iostream> using namespace std;

int main() {

int fab[55]={1,2,3,4,6}; int i,n;

for (i = 5 ; i < 55 ; i++) fab[i] = fab[i - 1] + fab[i - 3];

while (cin>>n&&n) {

printf("%d\\n", fab[n - 1]); }

return 0; }

钥匙计数之一

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 0 Accepted Submission(s) : 0 Problem Description

一把锁匙有N个槽，槽深为1，2，3，4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。

Input

本题无输入

Output

对N>=2且N<=31，输出满足要求的锁匙的总数。

Sample Output

N=2: 0N=3: 8N=4: 64N=5: 360..............N=31: ...注：根据Pku Judge Online 1351 Number of Locks或 Xi'an 2002 改编,在那里N<=16

Author

ecjtu_zhousc

递推方程式如下

1：如果X是钥匙， 则X1/2/3/4也是， 所以a[I]=a[I-1]*4

2: 如果X不是， X2/3是则X由1/4组成， 但要除去全1和全4， 所以a[I]+=(2^(I-1)-2)*2

后缀2或者3加上就成为钥匙的话，必然是没满足需要3个不同深度槽这一项，故X必然由1/4组成

3 如果X不是 X1/4是。则X=Y（1/4） M=X1/4=Y（4/1）（1/4）

前I-2位可以是1234，但要除去全为1/4的情况 还有就是X是钥匙且X是以1/4结尾

的情况。我们用b[I]数组表示i位时以1/4结尾的的数量

temp=（4^(i-2)-2^(i-2)）* 2 - b[i-1];

则 b[i]=a[i-1]*2+temp;

#include<stdio.h> #include<math.h>

int main () {

int i;

__int64 temp, a[32], b[32]; //b[i]记录以1 4结尾的数

a[2] = 0;

a[3] = 8; b[2] = 0; b[3] = 4;

printf ("N=2: 0\\nN=3: 8\\n"); for (i = 4; i <= 31; i++) {

a[i] = a[i - 1] * 4;

a[i] += (__int64) pow (2,i) - 4; //以2 3 结尾的

temp = ((__int64) pow (4,i-2) - (__int64) pow (2, i - 2)) * 2 - b[i - 1]; a[i] += temp;

b[i] = a[i - 1] * 2 + temp;

printf ("N=%d: %I64d\\n", i, a[i]); }

return 0; }

钥匙计数之二

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 0 Accepted Submission(s) : 0 Problem Description

一把钥匙有N个槽，2<N<26槽深为1，2，3，4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。

Input

本题无输入

Output

对2<N<26，输出满足要求的钥匙的总数。

Sample Output

N=3: 104N=4: 904N=5: 5880.....N=25: 8310566473196300280

张志坚，华东交通大学ACM退役队员

设lock[i]表示：有 i个槽的钥匙的个数

设one[i]表示：有 i个槽且左边第一个槽深度为1的钥匙的个数 设two[i]表示：有 i个槽且左边第一个槽深度为2的钥匙的个数 .. ..

设six[i]表示：有 i个槽且左边第一个槽深度为6的钥匙的个数

则显然：lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i]

由于易知：one[i]=six[i],two[i]=three[i]=four[i]=five[i] 则可以得到：lock[i]=one[i]*2+two[i]*4

其中：

one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i]; =one[i-1]+two[i-1]*4 +a[i]

two[i]=one[i-1]*2+two[i-1]*4 +b[i]

其中，a[i] 和b[i]的含义分别是： a[i]表示“有 i个槽且左边第一个槽深度为1，同时这种钥匙在除掉第一个槽后不再是钥匙”的钥匙的个数。

例如 123,124,125,134,135,145,126,136,146,156 就属于这种情况。

b[i]表示“有 i个槽且左边第一个槽深度为2，同时这种钥匙在除掉第一个槽后不再是钥匙” 的钥匙的个数。

分析到这里，可以知道，关键的是求a[i]和b[i]，我们可以得到如下表达式： a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4

b[i]=(2^(i-1)-2)*9

其中，a[i] 的各部分的含义如下： (2^(i-1)-2)*6： 当去掉第一位，后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)两种数字的时候，显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然还需要去掉两种特殊情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面六种组合，所以得到(2^(i-1)-2)*6。 (2^(i-2)-1)*4：

当去掉第一位，后面i-1位只有 (2,6)或者 (3,6) 或者(4,6) 或者(5，6)两种数字的时候，显然是不合法的钥匙（不满足至少有3个

不同的深度），加上第一位的1则“可能”是一个合格的钥匙。因为要注意满足“相连的槽其深度之差不得为5”这个条件，所以，紧跟着1的绝对不能是6，这样，相对于上面的分析，后面i-2位可以是每组中的任意一个，所以有2^(i-2)，还要减去1是因为同样要排除后面全部是和第2位一样的数字这样的情况。满足这种条件的一共有上面的四种组合，所以得到(2^(i-2)-1)*4。

b[i] 的含义如下： (2^(i-1)-2)*9： 当去掉第一位，后面i-1位只有 (1,3)或者 (1,4) 或者(1,5) 或者(3,4) 或者(3,5) 或者(3,6) 或者(4,5) 或者(4,6) 或者(5,6) 两种数字的时候，显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然还需要去掉两种特殊情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面9种组合，所以得到(2^(i-1)-2)*9。

目前为止，我们可以求出所有的a[i]和b[i]，而且知道了递推关系，只要再做一点简单的工作就可以了，那就是还需要初始值，当然，很容易枚举出最简单的情况

one[3]=16; two[3]=18;

这样，整个问题就解决了。 特别说明：

这种递推的题目，就是从f(i-1) 加一个元素，然后枚举出所有可能的情况，推导到f(i),当然这个题目有点麻烦，但是套路是一样的，大家也可以参考一下以前的special number课件,里面对于hdoj_1133 Buy the Ticket这个题目的分析，里面的思路和这个完全一样。

#include<stdio.h> #include<limits.h> #include<math.h> #include<float.h> _int64 t1[27],t2[27]; _int64 a,b; int main() { int i; t1[3]=16; t2[3]=18;

printf("N=3: 104\\n"); for(i=4;i<=25;i++) {

a=((__int64)pow(2,i-1)-2)*6+((__int64)pow(2,i-2)-1)*4; b=((__int64)pow(2,i-1)-2)*9; t1[i]=t1[i-1]+t2[i-1]*4+a; t2[i]=t1[i-1]*2+t2[i-1]*4+b;

printf("N=%d: %I64d\\n",i,t1[i]*2+t2[i]*4); }

return 0; }

本文来源：https://www.bwwdw.com/article/5ria.html