首页 > ACM题库 > HDU-杭电 > hdu 2047 阿牛的EOF牛肉串-递推-[解题报告]C++
2013
12-26

hdu 2047 阿牛的EOF牛肉串-递推-[解题报告]C++

阿牛的EOF牛肉串

问题描述 :

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

你,NEW ACMer,EOF的崇拜者,能帮阿牛算一下一共有多少种满足要求的不同的字符串吗?

PS: 阿牛还有一个小秘密,就是准备把这个刻有 EOF的牛肉干,作为神秘礼物献给杭电五十周年校庆,可以想象,当校长接过这块牛肉干的时候该有多高兴!这里,请允许我代表杭电的ACMer向阿牛表示感谢!

再次感谢!

输入:

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

输出:

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

样例输入:

1
2

样例输出:

3
8

原题:
http://acm.hdu.edu.cn/showproblem.php?pid=2047

分析:

      分析题意,我们知道这是一道排列计数问题。而且,题意的要求是对于给定字符串长度n,给出对应的方案数m。我很容易联想到“f(n) = m”这样的函数关系。并且,题目中的限制条件只有“两个O不能相邻”。计数 + 简单限制 = 递推。接下来的问题就是求出递推公式了。

* 第n格取“O”:

———————————-
|   |   |   | …… |     |     |  O  |
———————————-
 1   2   3          n-2 n-1   n

    ———————————–
    |   |   |   | …… |     |  E  |  O  |
    ———————————–
      1   2   3         n-2  n-1   n

    ———————————–
    |   |   |   | …… |     |  F  |  O  |
    ———————————–
      1   2   3         n-2  n-1   n

      对于第n格取“O”的情况,为了保证两个“O”不相邻,n-1格有两种可能,即“E”、“F”。对于余下的n-2格,由于第n-1格不取“O”,所以第n-2格不受n-1格的限制。其排列数等于f(n-2)。

* 第n格不取“O”:
———————————-
|   |   |   | …… |     |     |  E  |
———————————-
  1   2   3         n-2  n-1  n

———————————-
|   |   |   | …… |     |     |  F  |
———————————-
  1   2   3         n-2  n-1  n

      对于第n格不取“O”的情况,即取“E”、“F”。对于余下的n-1格,由于第n格不取“O”,所以,第n-1格不受n格的限制。其排列数等于f(n-1)。

      综上,f(n) = 2*f(n-2) + 2*f(n-1)
           = 2*(f(n-2) + f(n-1))

      这里,再说明一下“第n-1格不受n格的限制”这样一个条件。例如,n=4。如果,第4格取“O”,那么剩下的3格的方案数是多少呢??肯定不是f(3)。因为,当n=3时,即只有3格的时候,第3格是可以取“O”的。而例子中的3格中,第3格很明显不能取“O”。所以,剩下的3格方案数不是f(3)。如果,第4格取“E”或者“F”,那么剩下的3格的方案数又是多少呢??肯定是f(3)。这就是,是否受限制的差别。这是在递归中很重要的一个概念——什么是子结构。大家在日常的训练中要多加注意,不能盲目的识别子结构。

源程序:(VC++ 6.0)

#include<stdio.h>
#include<string.h>

const int MAX = 40;

__int64 seq[MAX];

void GenerateSeq(__int64 seq[], int n);

int main()
{
	//freopen("input.txt", "r", stdin);
	int n;
	memset(seq, 0, sizeof(seq));
	GenerateSeq(seq, MAX);
	while(scanf("%d", &n) != EOF)
	{
		printf("%I64d/n", seq[n]);
	}
	return 0;
}

void GenerateSeq(__int64 seq[], int n)
{
	seq[1] = 3;
	seq[2] = 8;
	int i;
	for(i = 3; i < n; i++)
	{
		seq[i] = 2 * (seq[i - 2] + seq[i - 1]);
	}
}

解题转自:http://blog.csdn.net/lostaway/article/details/5742571


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])