P1164-小A点菜

这篇具有很好参考价值的文章主要介绍了P1164-小A点菜。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#include<iostream>
using namespace std;
const long long N = 1e5 + 9;
int dp[1000][1000];
int a[N];
int main() {
	long long m, n,ans=0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i <= n; i++) {
		dp[i][0] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j >= a[i]) {
				dp[i][j] += dp[i - 1][j - a[i]];
			}
			dp[i][j] += dp[i - 1][j];
		}
	}
	cout << dp[n][m];
	return 0;
}

\(line :11\) 为所有花费 0 元的商品的方法赋值为 1; 因为花费0元的方法,有且仅有一种,那就是都不买

\(line:13-14\) 两次循环,外循环为商品的数目,内循环为 花费的钱 ,即表示 每 \(i:(1\to n)\) 件商品 花费 \(j:(1 \to m)\) 元 的方法数, 先历遍商品数.(动态规划的方程为$ dp[i][j] += dp[i - 1][j - a[i]]$ 就是通过 \(i-1\) 的数目推出 \(i\) 的数目,所以先历遍商品数)

if (j >= a[i]) {                     
	dp[i][j] += dp[i - 1][j - a[i]];
}
dp[i][j] += dp[i - 1][j];

其中 \(dp[ i ][ j ]\) 表示前 \(i\) 个商品花费 $ j $ 元的方法数.

\(dp[i][j]\)一共有两种情况:

  1. 买第 \(i\) 件商品 : \(dp[i][j] += dp[i - 1][j - a[i]]\) 相当于 在 前 \(i-1\) 件商品 花费 \(j-a[i]\) 元 的基础之上 卖下了花费\(a[i]\) 元的 \(i\) 这件商品(前提是\(j>= a[i]\) 可以买)
  2. 不买第 \(i\) 件商品:$dp[i][j] += dp[i - 1][j] $ 那么就表示 前\(i\) 件商品 和前 \(i-1\) 件商品一样 花费了 \(j\)

因为求的是方法,所以两种情况都要加上, 其中不买 \(i\) 这件商品 这种情况一定存在

最后输出 \(dp[n][m]\) ,即一共 \(n\) 件商品 花费 m元的方法

优化为一维数组

为何可以优化?:

​ 每次循环只用到了 \(i\) 的上一个 \(i-1\)

所以由 \(dp[i][j]\) 可以变为 \(dp[j]\)

#include<iostream>
using namespace std;
const long long N = 1e5 + 9;
int dp[N];
int a[N];
int main() {
	long long m, n, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
		dp[0]= 1;//表示最初始的那个,第一个商品花费0元的方法为1;
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 1; j--) {//注意这里要反过来应为dp[j-a[i]]可能已经改变了
         	//这里省略了一步就是 dp[j]=dp[j] 这表示 不买的情况,下一个和上一个的方法数是一样的
			if (j >= a[i]) {
				dp[j] += dp[j - a[i]];//逐渐迭代
			}
		}
	}
	cout << dp[m];
	return 0;
}

\(line:15\) 一维的 \(dp[j] += dp[j - a[i]]\) 对比 二维的 \(dp[i] [j] += dp[i - 1] [j - a[i]]\)文章来源地址https://www.toymoban.com/news/detail-779481.html

  • \(dp[j] += dp[j - a[i]]\) , 表示 花费\(j-a[i]\)元可以卖下前\(i-1\)个商品 的方法数的基础上 买下\(i\)这件商品的方法数,直接覆盖掉 \(dp:i-1\)
  • 所以要倒过来历遍\(j:(m\to 1)\),以防 \(dp[j-a[i]]\) 被覆盖了

到了这里,关于P1164-小A点菜的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 点菜问题:动态规划(C语言实现)

    目录 1.题目概述: 2.题目解析:  3.题目代码: 4.样例展示: 5.题目总结:          某实验室经常有活动需要叫外卖,但是每次叫外卖报销的经费总额最大为C元,有N种菜可以点,经过长时间的点菜,实验室对每种菜i都有一个量化的评分Vi,这种菜的价格为Pi,问如何选择

    2024年02月07日
    浏览(38)
  • PAT 1164 Good in C 测试点3,4

    个人学习记录,代码难免不尽人意。 When your interviewer asks you to write “Hello World” using C, can you do as the following figure shows? Input Specification: Each input file contains one test case. For each case, the first part gives the 26 capital English letters A-Z, each in a 7×5 matrix of C’s and .\\\'s. Then a sentence is given in a

    2024年02月09日
    浏览(63)
  • EG1164大功率同步整流升压模块开源,最高效率97%

    EG1164大功率同步整流Boost升压电源模块,最高效率97%,输入电压8~50V,输出电压8~60V可调,最大功率300瓦以上,开关频率219kHz。 白嫖了张嘉立创的彩色丝印券就随便画了个板试试,第一次打彩色丝印。 因为我测试设备有限(电源和负载都是最大300W),所以没法测更大功率,这

    2024年02月09日
    浏览(36)
  • 【pyqt6】用pyqt做一个点菜小程序

    在本文中,我们将使用 PyQt6(Python的GUI库)创建一个简单的点菜小程序。该程序允许用户从菜单中选择菜品,将其添加到订单中,并通过点击“下单”按钮查看订单的总价。 随着Python在不同领域的应用不断增加,开发GUI应用程序成为一项重要的技能。PyQt是一个强大的工具,

    2024年01月25日
    浏览(47)
  • 案例005:基于小程序的电子点菜系统开发设计与实现

    文末获取源码 开发语言:Java 框架:SSM JDK版本:JDK1.8 数据库:mysql 5.7 开发软件:eclipse/myeclipse/idea Maven包:Maven3.5.4 小程序框架:uniapp 小程序开发软件:HBuilder X 小程序运行软件:微信开发者 目录 前言 系统展示 用户注册用户功能实现 管理员功能实现 代码实现 登录功能实现

    2024年02月04日
    浏览(42)
  • 基于小程序的老孙电子点菜系统开发设计与实现+ssm

    中国有着五千年文化历史,传统的食谱已经不能和现代化的社会相结合,所以我想开发一套关于食谱方面的毕业设计,随着人们对健康的关注,食物的营养高低也越来越重视,但大部份人关心的是某种单一的食物有什么营养,而忽略了吃饭方试是否健康,下面是我为大家推荐

    2024年01月22日
    浏览(39)
  • 【Docker】Linux路由连接两个不同网段namespace,连接namespace与主机

    如果两个namespace处于不同的子网中,那么就不能通过bridge进行连接了,而是需要通过路由器进行三层转发。然而Linux并未像提供虚拟网桥一样也提供一个虚拟路由器设备,原因是Linux自身就具备有路由器功能。 路由器的工作原理是这样的:路由器上有2到多个网络接口,每个网

    2024年02月05日
    浏览(38)
  • C++中const char*、char const*和char * const的区别详解

       1、const char* p: 2、char const*:  等价于const char*; 用法如上,这里不过多解释  3、char * const: 4、const char * const p = str 等价于 char const * const p=str     p的指向不能改变,p指向的内容也不能被改变; 5、 补充:

    2024年02月04日
    浏览(42)
  • 【Docker 内核详解】namespace 资源隔离(一):进行 namespace API 操作的 4 种方式

    【Docker 内核详解 - namespace 资源隔离】 系列包含: namespace 资源隔离(一):进行 namespace API 操作的 4 种方式 namespace 资源隔离(二):UTS namespace IPC namespace namespace 资源隔离(三):PID namespace namespace 资源隔离(四):Mount namespace Network namespace namespace 资源隔离(五):User

    2024年02月06日
    浏览(42)
  • 【C++】命名空间 ( namespace )

    命名空间是一种用来避免命名冲突的机制,它可以将一段代码的名称隔离开,使其与其他代码的名称不冲突; 命名空间的原理是将一个全局的作用域分成一个个命名空间,每个命名空间是个单独的作用域,同时若是在同一个作用域内可能出现的命名冲突也不会造成影响,有效

    2024年02月04日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包