首页 > 其他分享 >蓝桥杯练习题总结(三)线性dp题(摆花、数字三角形加强版)

蓝桥杯练习题总结(三)线性dp题(摆花、数字三角形加强版)

时间:2024-03-26 23:58:07浏览次数:31  
标签:练习题 摆花 遍历 int 摆放 蓝桥 种花 dp

目录

 

一、摆花

思路一:

 确定状态:

初始化:

思路二:

确定状态:

初始化:

循环遍历:

 状态转移方程:

 二、数字三角形加强版


一、摆花

题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展出更多种花,规定第i种花不能超过αi盆。摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算,一共有多少种不同的摆花方案。

输入描述

第一行包含两个正整数n和m,中间用一个空格隔开。

第二行有n个整数,每两个整数之间用一个空格隔开,依次表示a1、a2、...、an。

其中,0 < n ≤ 100,0 < m ≤ 100,0 ≤ ai ≤ 100。

输出描述

输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对10^9 + 7取模的结果。

输入样例

2 4 3 2

输出样例

2

解题思路

思路一:

 确定状态:

首先,需要明确问题的要求:给定n种不同的花和每种花的最大数量限制,求出在摆放m盆花时,能够形成的不同摆花方案数。这个问题的关键在于每种花可以选择摆放的数量从0到其最大限制,且摆放的花必须按照花的种类顺序排列。

在动态规划中,定义状态是至关重要的一步。这里,我们定义状态dp[i][j]为考虑前i种花时,摆放j盆花的不同方案数。

int n, m; cin >> n >> m;
vector<int>a(n + 1);
vector<vector<int> >dp(101, vector<int>(101));

初始化:

初始化第一种花的情况,因为只有一种花,所以可以从0到a[1]朵任意选择,都只有一种方式

for (int i = 0; i <= a[1]; i++) dp[1][i] = 1;
  • 外层循环遍历花的种类:从1到n,(花的种类为0时情况已初始化)对每种花进行遍历。

  • 中层循环遍历目标花的总数:从0到m,对可能摆放的花的总数进行遍历。

  • 在内层循环中,再加一个循环遍历当前考虑的这种花可以选择的数量(从0到该种花的数量上限或剩余可摆放数量的较小值),这里通过检查j - k >= 0来确保不会有负数的情况发生。
 for (int i = 2; i <= n; i++) { // 遍历每一种花 
        for (int j = 0; j <= m; j++) { // 遍历当前要选的花的总数
            for (int k = 0; k <= a[i] && j - k >= 0; k++) {
                    ......
            }
        }
    }
  • 状态转移方程dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;的含义是,要得到前i种花中摆放j盆花的方案数,需要将所有可能包含第i种花的数量(从0到a[i])的方案数加起来。每次更新dp[i][j]时,都要对p取模,以避免整数溢出并满足题目要求。
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;
#include <bits/stdc++.h>
using namespace std;
const int N = 200, p = 1e6 + 7;
int dp[N][N], n, m, a[N];

int main()
{
    cin >> n >> m;// 输入花的种类数n和目标数m
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 输入每种花的数量
    for (int i = 0; i <= a[1]; i++) dp[1][i] = 1;
    // 初始化第一种花的情况,因为只有一种花,所以可以从0到a[1]朵任意选择,都只有一种方式

    // 动态规划填表过程
    for (int i = 2; i <= n; i++) { // 遍历每一种花 
        for (int j = 0; j <= m; j++) { // 遍历当前要选的花的总数
            for (int k = 0; k <= a[i] && j - k >= 0; k++) {
            // 状态转移方程:dp[i][j]表示前i种花选出j朵的方式数,它等于前i - 1种花选出j - k朵的方式数之和
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;
            }
        }
    }
    cout << dp[n][m];// 输出结果,即前n种花选出m朵的方式数(模p意义下)
    return 0;
}

思路二:

确定状态:

首先,需要明确问题的要求:给定n种不同的花和每种花的最大数量限制,求出在摆放m盆花时,能够形成的不同摆花方案数。这个问题的关键在于每种花可以选择摆放的数量从0到其最大限制,且摆放的花必须按照花的种类顺序排列。

在动态规划中,定义状态是至关重要的一步。这里,我们定义状态dp[i][j]为考虑前i种花时,摆放j盆花的不同方案数。

int n, m; cin >> n >> m;
vector<int>a(n + 1);
vector<vector<int> >dp(101, vector<int>(101));

初始化:

对于本问题,我们知道不摆放任何花(即j=0时)只有一种方案,即什么花都不摆。因此,初始化dp[0][0] = 1,表示没有花时,摆放0盆花的方案数为1。其他情况(即当j>0时),在没有考虑任何花的情况下是不可能摆放任何花的,这些状态默认为0,反映了不可能发生的情况。

dp[0][0] = 1;

循环遍历:

  • 外层循环遍历花的种类:从1到n,(花的种类为0时情况已初始化)对每种花进行遍历。

  • 中层循环遍历目标花的总数:从0到m,对可能摆放的花的总数进行遍历。

  • 内层循环遍历当前种类花的可能数量:从0到当前种类花的数量限制或j中的较小值(因为不可能摆放超过总数j的花)。这一步是优化的关键,通过只遍历到min(a[i], j)来减少不必要的计算。

for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k <= min(a[i],j); k++)
			{
                ......
			}
		}
	}

 状态转移方程:

dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;
#include <bits/stdc++.h>
using namespace std;
const int p = 1e6 + 7;

int main()
{
	int n, m; cin >> n >> m;
	vector<int>a(n + 1);
	vector<vector<int> >dp(101, vector<int>(101));
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k <= min(a[i],j); k++)
			{
				dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % p;
			}
		}
	}
	cout << dp[n][m] % p;
}

 二、数字三角形加强版

数字三角形最大路径和问题

给定一个数字三角形,从三角形的顶部到底部有多条不同的路径。对于每条路径,把路径上的数加起来可以得到一个和。任务是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过1。

输入描述:

输入的第一行包含一个整数N(1≤N≤100),表示三角形的行数。下面的N行给出数字三角形。数字三角形上的数都是0至100之间的整数。

输出描述:

输出一个整数,表示最大路径和。

输入输出样例:

输入:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出:

27

数字三角形

http://t.csdnimg.cn/2IdF4

此题与之前这题的不同点在与多了一个这样的要求:

  • 此外,向左下走的次数与向右下走的次数相差不能超过1。

意为:路径最后会停在最后一行中间的位置。此时有奇数和偶数两种情况,但是可以统一考虑为一种情况:

max(dp[n][(n + 1) / 2], dp[n][(n + 2) / 2]);

如果是奇数,那么两个数值相同;如果是偶数,取更大的一个,皆符合题意。

#include <iostream>
using namespace std;
int a[200][200], dp[200][200], n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			cin >> a[i][j];
	dp[1][1] = a[1][1];
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i; j++)
			dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1]);
	cout << max(dp[n][(n + 1) / 2], dp[n][(n + 2) / 2]);
	return 0;
}

今天就先到这了!!!

看到这里了还不给博主扣个:
⛳️ 点赞☀️收藏 ⭐️ 关注!

你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。

标签:练习题,摆花,遍历,int,摆放,蓝桥,种花,dp
From: https://blog.csdn.net/2301_79558858/article/details/137025861

相关文章

  • 扫地机器人 二分答案,贪心 蓝桥杯
    二分答案与二分查找类似,二分查找有一个前提就是数列要求是有序的,二分答案则是要求满足条件的答案是单调有序的,它的基本思想是在答案可能的范围([L,R])内二分查找答案,不断检查当前答案是否满足题目的要求,根据检查结果更新查找的区间,最终取得最符合题目要求的答案进行输出。......
  • 蓝桥杯 试题 基础练习 十进制转十六进制 C++
    问题描述十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号,分别表示十进制数的0至15。十六进制的计数方法是满16进1,所以十进制数16在十六进制中是10,而十进制的17在十六进制中是11,以此类推,十进制的30在十六进制......
  • 【蓝桥杯省赛真题33】python单词排序 中小学青少年组蓝桥杯比赛 算法思维python编程省
     目录python单词排序一、题目要求1、编程实现2、输入输出二、算法分析三、程序编写四、程序说明五、运行结果六、考点分析七、 推荐资料1、蓝桥杯比赛2、考级资料3、其它资料python单词排序第十三届蓝桥杯青少年组python比赛省赛真题一、题目要求(注:input......
  • 洛谷 P9237 [蓝桥杯 2023 省 A] 像素放置
    题意:n*m的方格,有的格子是数字,是数字的格子代表了相邻(包括自己)的9个格子内颜色值为1的格子有这么多个。给出这个方格,求满足条件的颜色方格,保证答案唯一。n<=10,m<=10。思路:想不出好办法,直接暴力+剪枝。暴力好说,01dfs即可,关键是如何剪枝。剪枝肯定是已经不会再变动颜色的......
  • [蓝桥杯 2013 国 C] 危险系数 dfs 深搜 递归
    ##题目背景抗日战争时期,冀中平原的地道战曾发挥重要作用。##题目描述地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。我们来定义一个危险系数$DF(x,y)$:对于两个站点$x$和$y(x\neqy),$如果能找到一......
  • 迷宫与陷阱(蓝桥杯)
    文章目录迷宫与陷阱问题描述bfs迷宫与陷阱问题描述小明在玩一款迷宫游戏,在游戏中他要控制自己的角色离开一间由NxN个格子组成的2D迷宫。小明的起始位置在左上角,他需要到达右下角的格子才能离开迷宫,每一步,他可以移动到上下左右相邻的格子中。迷宫中有些格子小......
  • 蓝桥杯刷题(十四)
    1.小平方代码n=int(input())count=0deff(x)->bool:#判断条件returnTrueifx**2%n<n/2elseFalseforiinrange(1,n):#遍历[1,n-1],符合题意计数加一iff(i):count+=1print(count)2.3的倍数代码a=int(input())b=int(input())......
  • 蓝桥杯算法基础(29)字符串匹配(RabinKarp)(KMP)(前缀树,字典树,trie,后缀数组,高度数组)
     RabinKarpRabinKarpS:ABABABm个P:ABBn个1.朴素算法,挨个匹配2.哈希法hash->滚动哈希c0*31^2+c1*31^1+c2类似于进制的求法求hash值(c0*31+c1)*31+c2hash(p)=o(n)hash(s)=o(m*n)privatestaticvoidmatch(Stringp,Strings){longhash_p=hash(p);......
  • 蓝桥杯n皇后问题C++
    用到了dfs算法#include<iostream>usingnamespacestd;intn;inta[10][10]={0};intsum=0;voidprin(inta[][10]){for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i][j]<......
  • 蓝桥杯算法集训 - Week 4:BFS、并查集、Flood Fill、哈希、单调栈/队列
    蓝桥杯算法集训-Week4本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、BFSBFS算法复习参考:BFS(Java)广度优先搜索简单介绍、模板、案例(一)Ⅰ、代码模板staticvoidbfs(Troot){//双端队列,用来存储元素D......