专栏首页程序编程之旅HDOJ/HDU 1297 Children’s Queue(推导~大数)

HDOJ/HDU 1297 Children’s Queue(推导~大数)

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

Sample Output 1 2 4

题意: 就是n个人,站成一排。 有一个要求,(F)女生不能单独一个人站在男生之间。 可以没有女生。

输出有多少种站法; (不考虑人与人的不同,只考虑位置和男女区别) (如果一排以MF结尾是不合法的)

分析: 假如n个人的站法为db[n]; 由前面的推导出db[n]。 db[n-1]结尾添加一个M,是一定可以的。 db[n-2]结尾添加FF,也是一定可以的。 添加MF不可以,添加MM也是可以的(但是这个情况和db[n-1]中重复了),添加FM也是和db[n-1]+M重复了。

在不可以序列后面加上FF(MF不可以,加上FF),成为合法, 所以db[n-4]后面+MFFF可以, 其实加一个F也能构成合法,但是这种情况包含在db[n-2](相当与+FF)里面;

所以递推方程式db[n] =db[n-1] + db[n-2] + db[n-4];

db[i] 中保存的都是合法序列数。

Java大数秒A~~~

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
    static BigInteger db[] = new BigInteger[1001];
    public static void main(String[] args) {
        dabiao();
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n =sc.nextInt();
            System.out.println(db[n]);
        }
    }
    private static void dabiao() {
        db[0]=new BigInteger("1");
        db[1]=new BigInteger("1");
        db[2]=new BigInteger("2");
        db[3]=new BigInteger("4");
        db[4]=new BigInteger("7");
        for(int i=5;i<db.length;i++){
            db[i]=db[i-1].add(db[i-2]).add(db[i-4]);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hdu----(5047)Sawtooth(大数相乘+数学推导)

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

    Gxjun
  • HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)

    谙忆
  • 字符串-AC自动机(详细图解)

    Fail指针 同KMP的next一样,Fail指针是AC自动机的核心,是在树上指出失配后下一个跳转的位置,而不用全部回溯,大大减少时间。那么Fail是怎么跳转...

    唔仄lo咚锵
  • 程序员进阶之算法练习(十三)

    前言 比赛就在这周末,这篇是比赛前最后一篇训练总结。 正文 hdu 5980(简单题) 题目大意 一个32位的数字,每个bytes包括8bit,所以一个整...

    落影
  • 这段时间的学习小结(1.17总结)

    去了新的环境学习,感觉还可以,当然因为期末刚结束的原因,导致这段时间有点松懈,后天就要回家了,还是非常开心的。

    dejavu1zz
  • 多元线性回归公式推导及R语言实现

    实际中有很多问题是一个因变量与多个自变量成线性相关,我们可以用一个多元线性回归方程来表示。

    知然
  • 客户端基本不用的算法系列:矩阵的递推关系分析

    数字是我们在编程中最常接触的元数据。无论是在业务还是刷题,多半部分都是数字的运算,其次是字符串,再次是布尔。

    用户2932962
  • 程序员也要有个好身体

    一年前就开始一些简单的健身了,但是都没有完全坚持下来,总是断断续续的,因此没有效果。原因其实只有一个————懒。 随着每天坐在电脑前的时间越来越长,颈椎、腰椎甚...

    GitOPEN
  • Nat. Biotechnol. | 多算法整合获取特定癌蛋白在特定肿瘤背景下的相互作用网络图

    大家好!今天推荐一篇Nature biotechnology的文章,“Oncoprotein-specific molecular interaction ma...

    DrugAI
  • 【腾讯实验室】推荐一些优秀的算法学习网站

    https://www.zhihu.com/question/20368410/answer/726247443

    统计学家
  • 其实算法就这么点东西

    以笔试为目的的修炼都是耍流氓。但也许,我们就想当个好流氓。秋招已到,希望大家都能收货满意的offer。

    程序员小浩
  • MQ消息堆积终极解决方案【RabbitMQ】

    如果架构中有用到mq,那就不可避免会遇到消息堆积的问题,因为我们没办法保证自己生产和消费永远都是正确的。像我们系统就遇到过很多次消息堆积情况,最严重的一次直接导...

    林老师带你学编程
  • 浅谈Laravel队列实现原理解决问题记录

    公司项目使用Laravel的开发的两个项目在同一个测试服务器部署,公用同一个redis。在使用laravel中的队列时,产生冲突干扰。

    用户8826052
  • Kubernetes 疑难杂症排查分享:神秘的溢出与丢包

    图片下载走的 k8s ingress,这个 ingress 路径对应后端 service 是一个代理静态图片文件的 nginx deployment,这个 de...

    imroc
  • 干货 | 携程一次Dubbo连接超时问题的排查

    顾海洋,携程框架架构研发部技术专家,负责携程分布式服务化领域的工作。目前主要负责 Dubbo 在携程的二次开发和推广工作。

    携程技术
  • 错排公式 详细解答

    错排问题:有n个正整数1,2,3,……n,将这n个正整数重新排列,使其中的每一个数都不在原来的位置上,这种排列称为正整数1,2,3,……n的错排,问这n个正整数...

    谙忆
  • 从Queue到Redis

    在Python中,进程之间互相隔离,但是在实际的工作中需要两个进程能够进行数据的通信,那么就可以通过队列和管道的方式来实现进程之间的通信,那么就可以使...

    无涯WuYa
  • 从小白到大神,你可能需要这么做!

    七八年前,我绝对是不会相信能够成为现在的自己,之前的我可以说是对计算机都一无所知的小白,而现在我已经就职于顶级互联网公司,并且已经获得数了十个数据挖掘比赛冠军,...

    崔庆才
  • java高并发系列 - 第25天:掌握JUC中的阻塞队列

    (2)如果操作失败,则返回特殊值(null或false,具体取决于操作),接口的常规结构如下表所示。

    路人甲Java

扫码关注云+社区

领取腾讯云代金券