当前位置:首页 > C++知识 > 正文内容

【题解】玩具

亿万年的星光2个月前 (12-28)C++知识129

【题目描述】

商店正在出售蒜头君最喜欢的系列玩具,在接下来的 " 周中,每周会出售其中的一款,同一款玩具不会重复出现。由于是蒜头君最喜欢的系列,他希望尽可能多地购买这些玩具,但是同一款玩具蒜头君只会购买一个。同时,蒜头君的预算只有元,因此他无法将每一款都纳入囊中。此外,蒜头君不能连续两周都购买玩具,否则他会陷入愧疚。现在蒜头君想知道,他最多可以买多少款不同的玩具呢?

【输入格式】

输入共2行:

第一行两个正整数几和 m,中间用一个空格隔开;

第二行共几个正整数,第i个正整数表示第:周出售的玩具的价格

【输出格式】

输出文件只有一行,包含一个整数,表示蒜头君最多能买多少款不同的玩具,

【数据范围】

对于 30%的数据,n< 10,m< 100;

对于 60%的数据,n< 100,m< 1000;

对于 100% 的数据,n< 1000,m< 50000,单个玩具的价格< 1000。

------------------------------

【题目分析】

很显然,这个题目是一个背包问题,我们设置 dp 数组为 dp|ij],表示第i周预算为j的最多可以买多少款不同的玩具。

通过转移方程 dp[i][j]= max(dp[i-1][j],dp[i-2][j-a[i]]+ 1);和 dp[i][j|= dp[i- 1][j]; 进行转移即可。


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:CSP复赛必备,时间与空间估算

没有最新的文章了...

相关文章

C++中双冒号(::)的用法

一、作用域符号前面一般是类名称,后面一般是该类的成员名称,C++为例避免不同的类有名称相同的成员而采用作用域的方式进行区分如:A,B表示两个类,在A,B中都有成员member。那么A::member就...

【数论】常见的距离度量方法

【数论】常见的距离度量方法

一、欧式距离欧式距离(Eucliden Metric,也是欧几里得度量)是一个通常采用的距离定义,旨在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点距离)。在二维和三维空间中的欧氏距...

树的遍历

在应用树结构解决问题时,往往要求按照某种此项获得树中全部结点的信息,这种操作叫做树的遍历。遍历的方法有很多种。常用的有:A. 先序遍历:先访问根结点,再从左到右按照先序思想遍历各子树。B. 后序遍历:...

unsigned

在一些代码中,经常能看到unsigned这种数据类型,比如下面这样的。#include<iostream> using namespace std; int&nbs...

【算法】单链表的一些操作(存取、查找、取出、插入、删除)

一、单链表结构的建立与输出#include<iostream> using namespace std; struct Node{ int ...

C++ 如何隐藏光标

在C++控制台做小游戏的时候,光标一直在闪,影响体验效果,我们可以通过下面的函数隐藏光标位置。void HideCursor(){ CONSOLE_CURSOR_INFO cu...