【算法训练(day1)】李白打酒加强版(dp问题)

这篇具有很好参考价值的文章主要介绍了【算法训练(day1)】李白打酒加强版(dp问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.题目描述

输入格式

输出格式

输入输出样例

说明/提示

二.解题思路

定义状态

推导状态方程

细节处理 

三.实现代码

四.小结一下


一.题目描述

话说大诗人李白,一生好饮。幸好他从不开车。

一天,他提着酒壶,从家里出来,酒壶中有酒 22 斗。他边走边唱:

无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。

这一路上,他一共遇到店 NN 次,遇到花 MM 次。已知最后一次遇到的是花,他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序,有多少种不同的可能?

注意:壶里没酒(00 斗)时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。

输入格式

第一行包含两个整数 NN 和 MM。

输出格式

输出一个整数表示答案。由于答案可能很大,输出模 10000000071000000007(即 109+7109+7)的结果。

输入输出样例

输入 #1复制

5 10

输出 #1复制

14

说明/提示

【样例说明】

如果我们用 0 代表遇到花,1 代表遇到店,1414 种顺序如下:

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

【评测用例规模与约定】

对于 40%40% 的评测用例:1≤N,M≤101≤N,M≤10。

对于 100%100% 的评测用例:1≤N,M≤1001≤N,M≤100。

蓝桥杯 2022 省赛 B 组 I 题。

二.解题思路

定义状态

这道题可以用dp求解,因为最后恰好喝完酒,并且没酒的时候遇到花是不合法的,这说明酒的最大数量不能大于花加起来的数量,如果酒的数量大于花的数量在最后就无法将所有的酒喝完,这是一个关键点。这样我们就需要记录下来酒的数量,花的数量,和经历的店的数量。我们可以用一个三维数组来表示,数组内存的是状态数,也就是走到当前位置有多少种方案。

推导状态方程

接下来我们需要推导出状态转移方程,我们用i表示走过的店,j表示走过的花 ,k表示走过的酒。当我们走到最后一步时有两种情况,是花还是店。这样划分就不会遗漏情况。【算法训练(day1)】李白打酒加强版(dp问题)

细节处理 

这里有个细节就是最后dp推到完毕取结果的时候不能直接取f[n][m][0],因为我们无法保证最后一步恰好是花,当最后一步为花时,最后一步和倒数第二步的组合数是一样的。还有个细节是dp过程中要加上自己本身的值,因为当有的时候前位置既可以是花又可以是店,我们需要把两个值加起来才是真正的值。

三.实现代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int f[110][110][110]; //店,花,酒
int main() {
    int m, n; // n是店的数量,m是花
    cin >> n >> m;
    f[0][0][2] = 1;
    for (int i = 0; i <= n; i++) 
    {
        for (int j = 0;j<=m;j++)
        {
            for(int k = 0;k<=m;k++)
            {
                if( i>0 && k%2==0)  //最后一步是店,说明走到最后一步时,店数加一,酒数翻倍,所以上一步酒数应该/2,并且店数应该比当前值小1
                {
                    f[i][j][k] = (f[i][j][k]+f[i-1][j][k/2])%1000000007;
                }
                if(j>0 && k>0)  //最后一步是花,说明走到当前值时,花数加一,酒数减一
                {//当前位置需要加上自身的值因为有可能会在上面进入从而导致初始值不是0
                    f[i][j][k] = (f[i][j][k]+f[i][j-1][k+1])%1000000007;
                }
            }
        }
    }
    cout<<f[n][m-1][1];  //不能直接取f[n][m][0],因为这样包含了最后遇到酒从0转移过来的情况,而题目要求最后一次必须是花,这时候最后一步和倒数第二步店方法数时一样的
    return 0;
}

四.小结一下

本质还是到dp,不过有多种限制条件,酒的数量和题目中的合法条件决定了dp状态,题眼是不能让酒的数量大于花的数量

  文章来源地址https://www.toymoban.com/news/detail-432118.html

到了这里,关于【算法训练(day1)】李白打酒加强版(dp问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • day1:前端缓存问题

    ❝ 「目标」 : 持续输出!每日分享关于web前端常见知识、面试题、性能优化、新技术等方面的内容。篇幅不会过长,方便理解和记忆。 ❞ ❝ 「主要面向群体:」 前端开发工程师(初、中、高级)、应届、转行、培训等同学 ❞ Day1-今日话题 「前端web项目缓存问题如何处理?

    2024年02月12日
    浏览(35)
  • 数据结构与算法学习(day1)

    (1)我是一个大三的学生(准确来说应该是准大三,因为明天才报名哈哈哈)。 (2)最近就想每天闲着没事也刷些C语言习题来锻炼下编程水平,也一直在思考企业对应届大学生能力的要求,所以经常会想到关于面试的事情。由于我也没实习过,所以我对面试没有一个具象化

    2024年02月10日
    浏览(49)
  • 算法初阶双指针+C语言期末考试之编程题加强训练

    常⻅的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针。 对撞指针:⼀般⽤于顺序结构中,也称左右指针。 • 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼 近。 • 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(

    2024年02月05日
    浏览(49)
  • 代码随想录算法练习Day1:二分查找

    题目链接:704. 二分查找 卡哥视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找 二分法概述: 二分法(Binary Search)是一种在有序数组或列表中查找目标元素的算法。 二分法使用前提 : 有序数组或列表 :二分法要求在查找的数据结

    2024年04月23日
    浏览(52)
  • 算法刷题Day1 二分查找+移除元素

    代码随想录-数组-1.数组理论基础 数组是存放在 连续内存空间 上的 相同类型 数据的 集合 优点:常数时间复杂度访问元素 缺点: 在删除或者增添元素的时候,就难免要移动其他元素的地址 ,时间复杂度为O(n) 代码随想录-数组-2.二分查找 前提条件 二分查找前提条件: 数组

    2024年02月10日
    浏览(52)
  • 数据结构与算法学习(day1)——简化版桶排序

    (1)我是一个大三的学生(准确来说应该是准大三,因为明天才报名哈哈哈)。 (2)最近就想每天闲着没事也刷些C语言习题来锻炼下编程水平,也一直在思考企业对应届大学生能力的要求,所以经常会想到关于面试的事情。由于我也没实习过,所以我对面试没有一个具象化

    2024年02月09日
    浏览(42)
  • dp算法篇Day7

     \\\"抱紧你的我,比国王富有~\\\"          从题目来看还是很容易理解的,就是找寻数组中构成差值相等的子序列。                        等差数列?这似乎和我们之前做的一个题类似。但是,那个题是给出了差值,但是这道题却没有。因此,这两道题的解法就很不一样

    2024年02月16日
    浏览(33)
  • 算法竞赛备赛进阶之数位DP训练

    数位DP的思想就是对每一位进行DP,计算时记忆化每一位可以有的状态,其作用是减少运算时间,避免重复计算。 数位DP是一种计数用的DP,一般就是要统计一个区间[A,B]内满足一些条件数的个数。 以1e9甚至1e18、1e100的问题为例,因为在统计情况下有很多重复的计算,数位DP实

    2024年01月16日
    浏览(48)
  • 算法刷题营【Day1】:: 704.二分查找:二分法详谈与相关刷题

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:704. 二分查找 2. 题解参考(模板写法) - - 2.1 方法一:左闭右闭写法 - - 2.2 方法二:左闭右开写法 3. 模板解释:左闭右闭 - - 3.1 区间划定 - - 3.2 left 、right 移动问题 - - 3.3 循环条件

    2024年02月04日
    浏览(45)
  • 【golang项目-GeeCache】动手写分布式缓存 day1 - 实现LRU算法

    【go项目-geecache】动手写分布式缓存 - day1 - 实现LRU算法 【go项目-geecache】动手写分布式缓存 - day2 - 单机并发缓存 【go项目-geecache】动手写分布式缓存 - day3 - HTTP 服务端 【go项目-geecache】动手写分布式缓存 - day4 - 一致性哈希(hash) 【go项目-geecache】动手写分布式缓存 - day5 - 分布

    2023年04月20日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包