网站开发常遇到客户问题,网站专题策划案例,苏州游玩攻略必去的地方,免费连网络的软件有哪些目录 一、摆花
思路一#xff1a; 确定状态#xff1a;
初始化#xff1a;
思路二#xff1a;
确定状态#xff1a;
初始化#xff1a;
循环遍历#xff1a; 状态转移方程#xff1a; 二、数字三角形加强版 一、摆花 题目描述 小明的花店新开张#xff0c;为了吸…目录 一、摆花
思路一 确定状态
初始化
思路二
确定状态
初始化
循环遍历 状态转移方程 二、数字三角形加强版 一、摆花 题目描述 小明的花店新开张为了吸引顾客他想在花店的门口摆上一排花共m盆。通过调查顾客的喜好小明列出了顾客最喜欢的n种花从1到n标号。为了在门口展出更多种花规定第i种花不能超过αi盆。摆花时同一种花放在一起且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算一共有多少种不同的摆花方案。 输入描述 第一行包含两个正整数n和m中间用一个空格隔开。 第二行有n个整数每两个整数之间用一个空格隔开依次表示a1、a2、...、an。 其中0 n ≤ 1000 m ≤ 1000 ≤ ai ≤ 100。 输出描述 输出只有一行一个整数表示有多少种方案。注意因为方案数可能很多请输出方案数对10^9 7取模的结果。 输入样例 2 4 3 2 输出样例 2 解题思路
思路一 确定状态
首先需要明确问题的要求给定n种不同的花和每种花的最大数量限制求出在摆放m盆花时能够形成的不同摆花方案数。这个问题的关键在于每种花可以选择摆放的数量从0到其最大限制且摆放的花必须按照花的种类顺序排列。 在动态规划中定义状态是至关重要的一步。这里我们定义状态dp[i][j]为考虑前i种花时摆放j盆花的不同方案数。
int n, m; cin n m;
vectorinta(n 1);
vectorvectorint dp(101, vectorint(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和目标数mfor (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;
vectorinta(n 1);
vectorvectorint dp(101, vectorint(101));
初始化
对于本问题我们知道不摆放任何花即j0时只有一种方案即什么花都不摆。因此初始化dp[0][0] 1表示没有花时摆放0盆花的方案数为1。其他情况即当j0时在没有考虑任何花的情况下是不可能摆放任何花的这些状态默认为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;vectorinta(n 1);vectorvectorint dp(101, vectorint(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。 输入描述 输入的第一行包含一个整数N1≤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;
}今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
