杭电 2047 阿牛的EOF牛肉串 (递推)「建议收藏」

杭电 2047 阿牛的EOF牛肉串 (递推)

大家好,又见面了,我是全栈君。

阿牛的EOF牛肉串

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 20247    Accepted Submission(s): 9495

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
   
   
1 2

 

Sample Output
   
   
3 8

 

Author
lcy
思路例如以下:
对于第n项:

当f(n-1)为o时。有两种可能即E,F;

当f(n-1)不是o,时,有三种可能E,O,F;

从图中能够看出:  
 


f(n-1)为o的情况=f(n-2)-(第n-1,n-2项都为o的情况,即f(n-2)*3-f(n-1))=f(n-1)-2*f(n-2);

f(n-1)不是0的情况=2*f(n-2);

所以:f(n)=2*(
f(n-1)-2*f(n-2) 
)+3*(
2*f(n-2) 


 
 
=2*f(n-1)+2*f(n-2);

难点:
关键是弄清楚递归的规律
代码例如以下:
#include<stdio.h>
int main()
{
 int n,i;
 __int64 a[66]={0,3,8};//由于后面的数值是直接与n相应的 所以a[0]应该复制为零,而不是三
 for(i=3;i<66;i++)
 {
  a[i]=2*a[i-1]+2*a[i-2];
 }
 while(~scanf("%d",&n))
 {
  printf("%I64d\n",a[n]);
 }
 return 0;
}
//由于牵扯到的数值较大 所以用__int64型

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115676.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 用PMML实现机器学习模型的跨平台上线

    用PMML实现机器学习模型的跨平台上线在机器学习用于产品的时候,我们经常会遇到跨平台的问题。比如我们用Python基于一系列的机器学习库训练了一个模型,但是有时候其他的产品和项目想把这个模型集成进去,但是这些产品很多只支持某些特定的生产环

  • ITextPDF7

    ITextPDF7ITextPDF前言版本说明itext7-core=7.1.13相关链接:itextpdf官网地址:https://itextpdf.com/enitextpdf官方文档:https://kb.itextpdf.com/home/it7kbitextpdf官方github地址:https://github.com/itext/itext7itextpdfmaven地址:https://mvnrepository.com/artifact/com.itextpdf/itext

  • 一年多的前后(2019vs2020)对比「建议收藏」

    一年多的前后(2019vs2020)对比「建议收藏」不知不觉,又到了这个躁动不安的季节,躁动的是应届毕业生毕业以及高考。关于对青春的情愫,通常在这种时刻都会有各种各样的故事,当然了,我并不是一个会讲故事的人,所以通常情况下,就采用这种总结性的方式写文字

  • 内网IP段有哪些_为什么有些内网使用公网地址段

    内网IP段有哪些_为什么有些内网使用公网地址段常见的内网IP段有:10.0.0.0/810.0.0.0-10.255.255.255172.16.0.0/12172.16.0.0-172.31.255.255192.168.0.0/16192.168.0.0-192.168.255.255以上三个网段分别属于A、B、C三类IP地址,来自《RFC1918》。但是根据《ReservedIPaddresses-Wikipedia,thefreeencyclopedia》及《RFC6890-Special

  • 一些sql三

    1、1=1,1=2的使用,在SQL语句组合时用的较多“where 1=1” 是表示选择全部“where 1=2”全部不选,如:if @strWhere&#1

    2021年12月25日
  • 鱼和水的故事

    鱼和水的故事,那两句对白很经典,几乎谁都知道,但却很少人知道故事的全篇。鱼说:“你看不见我眼中的泪,因为我在水中。” 水说:“我能感觉得到你的泪,因为你在我心中。”http://hove

    2021年12月25日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号