洛谷P1077摆花

news/2025/2/14 17:04:54/

文章目录

  • 一、题目描述
  • 二、思路
  • 三、代码

一、题目描述

https://www.luogu.com.cn/problem/P1077
题目描述很容易看懂

二、思路

动态规划题目,首先定义状态
dp[i][j]:摆前i种花,一共摆j盆的方案数。
i:1~n
j:1~m
需要注意的时,第i种花摆放的盆数范围是0~a[i].所以我们需要枚举 第
i种花 摆放多少盆。所以来一个三重循环。
状态转移方程:
k:1~a[i]&&k<m。dp[i][j]+=dp[i][j]+dp[i-1][j-k]
即在i,j确定的情况下,我们是需要枚举k,k为每次第i盆花放了k盆。
状态转移:第i盆花放了k盆,那么前i-1盆花就放了 j-k盆!

初始化:初始化个人感觉不是很容易,博主在这摔了跟头。因为我第一次的为dp[1][1]=1;一想感觉没什么问题。
但是dp[1][1]不一定等于1! 如果a[1]=0 的话 dp[1][1]就等于0了!!
所以初始化为 dp[0][0]=1 。从第一行i=1 而不再是i=2开始。

还要注意 取模1000007


滚动数组:
来一手滚动数组 将二维变一维。也就是覆盖 将这一行的值覆盖上一行。
对于滚动数组,我们就要思考 是正推还是逆推
状态转移时,对于每一行,我们都需要上一行前面的值,所以我们要逆推!
防止前面的值先被覆盖。
初始化 仍然dp[0]=1;
但是注意这里 k 一定要从1开始。
因为我们初始化时dp[0]=1的含义已经包含了 第i种花 一个也没选的情况

三、代码

#include <iostream>
#include <cstdio>
using namespace std;int main(){int n,m,a[105],dp[105][105]={0};scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&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<=a[i]&&k<=j;k++){dp[i][j]=(dp[i][j]+dp[i-1][j-k])%1000007;}}}printf("%d",dp[n][m]);return 0;
}

滚动数组:

#include <iostream>
#include <cstdio>
using namespace std;int main(){int n,m,a[105],dp[105]={0};scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);dp[0]=1;for(int i=1;i<=n;i++){//一定要逆推for(int j=m;j>=0;j--){for(int k=1;k<=a[i]&&k<=j;k++){dp[j]=(dp[j]+dp[j-k])%1000007;}}}printf("%d",dp[m]);return 0;
}

http://www.ppmy.cn/news/628799.html

相关文章

IP地点定位为什么有误差?

随着互联网的不断普及&#xff0c;人们对IP地点定位需求越来越多。然而&#xff0c;即便是在现代技术的支持下IP地点定位仍然存在误差。那么&#xff0c;IP地点定位为什么会出现误差呢&#xff1f; IP&#xff08;Internet Protocol&#xff09;地址是指互联网协议&#xff08;…

数据库技术之MySQL高级

目录 子查询与表连接 子查询(嵌套sql) 利⽤⼦查询进⾏过滤 作为计算字段使⽤⼦查询 外键 表关系 关系表 表联结 联结多个表 使⽤表别名 AS 组合查询 UNION 总结&#xff1a;表联结 练习题 sql_mode sql_mode值的含义 MySQL事务 概述 ⼀,事务的语法 ⼆,事务的…

一篇博客帮你了解MySQL高级知识

MySQL高级 一、子查询与表连接子查询&#xff08;嵌套SQL&#xff09;关系表组合查询 UNION 二、MySQL事务概述事务的语法事务的ACID特性事物的并发问题事物的的隔离级别不同隔离级别的锁的情况&#xff08;了解&#xff09;隐式提交&#xff08;了解&#xff09; 三、MySQL中的…

构建高并发平台架构

一、 设计理念 1. 空间换时间 1) 多级缓存&#xff0c;静态化 客户端页面缓存&#xff08;http header中包含Expires/Cache of Control&#xff0c;last modified(304&#xff0c;server不返回body&#xff0c;客户端可以继续用cache&#xff0c;减少流量)&#xf…

高并发高可用的 架构实践

高并发高可用的 架构实践 一、 设计理念 1.空间换时间 1)多级缓存&#xff0c;静态化 客户端页面缓存&#xff08;http header中包含Expires/Cache of Control&#xff0c;last modified(304&#xff0c;server不返回body&#xff0c;客户端可以继续用cache&#xff0c;减少流量…

局部非饱和性的含义_范里安-微观经济学现代观点讲义(new)

《范里安-微观经济学现代观点讲义(new)》由会员分享,可在线阅读,更多相关《范里安-微观经济学现代观点讲义(new)(114页珍藏版)》请在人人文库网上搜索。 1、Chapter one: Introduction一、资源的稀缺性与合理配置对于消费者和厂商等微观个体来说,其所拥有的经济资源的稀缺性…

构建高并发高可用的架构

从各个角度总结了电商平台中的架构实践&#xff0c;由于时间仓促&#xff0c;定了个初稿&#xff0c;待补充完善&#xff0c;欢迎大家一起交流。 转载请声明出处&#xff1a;http://blog.csdn.net/yangbutao/article/details/12242441 作者&#xff1a;杨步涛 关注分布式架构、…

[架构之路-182]-《软考-系统分析师》-19- 系统可靠性分析与设计 - 概览

前言&#xff1a; 可靠性工程是研究产品生命周期中故障的发生、发展规律&#xff0c;达到预防故障&#xff0c;消灭故 障&#xff0c;提高产品可用性的工程技术。 信息系统的可靠性是指系统在满足一定条件的应用环境中能够正常工作的能力&#xff0c;可以按一般工程系统的可靠性…