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日
    浏览(46)
  • 动态规划-树形DP

    链接:https://www.acwing.com/problem/content/848/ 给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1 sim n 1 ∼ n )和 n − 1 n-1 n − 1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩

    2024年02月08日
    浏览(38)
  • 动态规划之树形DP

    树形DP是指在“树”这种数据结构上进行的动态规划:给出一颗树,要求以最少的代价(或取得最大收益)完成给定的操作。通常这类问题规模比较大,枚举算法效率低,无法胜任,贪心算法不能求得最优解,因此需要用动态规划进行求解。 在树上做动态规划显得非常合适,

    2024年02月05日
    浏览(44)
  • 动态规划【DP】详细解释

    动态规划,英文简称DP,是一种常见的算法设计思想。 它通常被应用于需要求解最优化问题的场景中。其核心思想是将原问题分解成若干个子问题进行求解,并将子问题的解记录下来,避免重复计算。 动态规划的常见四步骤为:定义状态;设计状态转移方程;给定边界条件;

    2024年02月05日
    浏览(37)
  • 动态规划(一)一维DP

    通过上篇文章,动态规划(零)入门概念相信大家已经对动态规划有了一些概念上的理解,那么如何运用动态规划去解决问题呢,首先要知道动态规划的解题步骤。 动态规划的步骤如下: (1) 设计状态 (2) 写出状态转移方程 (3) 设定初始状态 (4) 执行状态转移 (5) 返回最终的解 下

    2024年02月07日
    浏览(38)
  • 【dp动态规划】印章

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

    2024年02月02日
    浏览(51)
  • 动态规划dp-过河卒

    A点有一个过河卒,需要走到目标B点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的 C 点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图℃ 点上的马可以控制9个点(图中的P1,P2...P8和C)。卒不能通过对方马的控制点

    2024年04月11日
    浏览(39)
  • 算法——动态规划(DP)——递推

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

    2024年01月20日
    浏览(55)
  • DP算法:动态规划算法

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

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

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

    2024年02月04日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包