I 李白打酒加强版 / 动态规划dp

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

李白打酒加强版

题目描述
话说大诗人李白,一生好饮。幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店 N 次,遇到花 M 次。
已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序,有多少种不同的可能?
注意:壶里没酒( 0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。

输入格式
输入包含多组测试数据。
第一行为T,表示存在T组测试数据,T不超过30。
对于每组测试数据,输入两个整数N 和M.
1 ≤ N, M ≤ 100。

输出格式
输出一个整数表示答案。由于答案可能很大,输出模1000000007 的结果。

输入样例
5 10

输出样例
14

动态规划dp

思路:a[i][j][k]表示走到了第i家店,遇到了j朵花,酒的数量为k,然后就可以转移了

  1. f(i - 1, j, k / 2):遇到的是店,说明此前遇到店的数量为i - 1,遇到花的数量仍然为j,酒壶中酒的数量为k/2;满足条件i大于等于1,k能被二整除
  2. f(i, j - 1, k + 1):遇到的是花,说明此前遇到店的数量为i,遇到花的数量为j - 1,酒壶中酒的数量为k + 1。满足条件j大于等于1

注意转移的条件,然后i和j要从0开始遍历,还有结果是
a[n][m-1][1]才能保证最后一个是花且刚好酒为0文章来源地址https://www.toymoban.com/news/detail-412052.html

#include <bits/stdc++.h>
using namespace std;
int a[105][105][105];
const int MOD=1e9+7;
int main()
{
  int n,m;
  cin>>n>>m;
  a[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>=1&&k%2==0) a[i][j][k]=(a[i][j][k]+a[i-1][j][k/2])%MOD;
        if(j>=1) a[i][j][k]=(a[i][j][k]+a[i][j-1][k+1])%MOD;
      }
    }
  }
  cout<<a[n][m-1][1]<<endl;
  return 0;
}

到了这里,关于I 李白打酒加强版 / 动态规划dp的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 动态规划报告(树形DP+概率DP

    树形 DP,即在树上进行的 DP。由于树固有的递归性质,树形 DP 一般都是递归进行的。一般需要在遍历树的同时维护所需的信息 以一道题目为例 2022CCPC桂林站G Group Homework No, we don’t want group homework. It’s the place where 1+11 can be true. However, you are currently the leader of a group with three

    2024年02月12日
    浏览(48)
  • 动态规划:线性DP

    2024年02月06日
    浏览(41)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(57)
  • 动态规划入门(DP)

    目录 1.DP概念和编程方法 1.1.DP概念 例如: 1.1.1.重叠子问题 1.1.2.最优子结构 “无后效性” 1.2.DP的两种编程方法 1.2.1.自顶向下与记忆化 1.2.2.自底向上与制表递推 对比两种方法 1.3.DP的设计和实现(0/1背包问题) 例题: Bone collector(hdu 2606) Problem Description Input Output Sample Inpu

    2024年02月19日
    浏览(38)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(51)
  • ★动态规划(DP算法)详解

    什么是动态规划:动态规划_百度百科 内容太多了不作介绍,重点部分是无后效性,重叠子问题,最优子结构。 问S-P1和S-P2有多少种路径数,毫无疑问可以先从S开始深搜两次,S-P1和S-P2找出所有路径数,但是当这个图足够大,那就会超时。 动态规划旨在用 空间换时间 ,我们

    2024年02月04日
    浏览(50)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(47)
  • 动态规划——线性DP

    暴力搜索:由可行的所有起点出发,搜索出所有的路径。 但是深搜的算法时间复杂度要达到 O ( 2 n ) O(2^n) O ( 2 n ) (每个数都有选或不选的两个选择),指数级的时间复杂度在本题中( n ≤ 100 n≤100 n ≤ 100 )显然是不能接受的。那么再观察这个这棵递归树,可以发现其中有很

    2024年01月19日
    浏览(48)
  • 【dp动态规划】印章

    共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。 一行两个正整数n和m 一个实数P表示答案,保留4位小数。 2 3 0.7500 python代码

    2024年02月02日
    浏览(60)
  • 动态规划-概率DP

    https://www.luogu.com.cn/problem/CF148D 袋子里有 w w w 只白鼠和 b b b 只黑鼠 ,A和B轮流从袋子里抓,谁先抓到白色谁就赢。A每次随机抓一只,B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则B赢。A先抓,问A赢的概率。 输入 一行两个数 w , b w,b w , b 。

    2024年02月08日
    浏览(29)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包