ECNUOJ 2143 端午节快乐
2024-08-30 20:39:52
端午节快乐
Time Limit:1000MS Memory Limit:65536KB
Total Submit:1720 Accepted:868
Description
有一段有趣的传说。公元前340年,爱国诗人、楚国大夫屈原,面临亡国之痛,于五月五日,悲愤地怀抱大石投汩罗江,为了不使鱼虾损伤他的躯体,人们纷纷用竹筒装米投入江中。以后,为了表示对屈原的崇敬和怀念,每到这一天,人们便用竹筒装米,投江祭奠,这就是我国最早的粽子——“筒粽”的由来。
今天是端午节,ECNU决定请大家吃粽子。恰好,今天超市为了迎合"端午节",推出了"端午大酬宾",即促销活动。严格的买三送一,买五送二。
ECNU想用现有的钱,买最多的粽子,但是他自己又不会算,所以希望你能帮帮他。
Input
输入第一行为一个数N(1<=N<=100),表示测试数据的组数。
每组测试数据有两个整数,A,B (0<=A<=1000,0<B<10)表示ECNU有A元钱,每个粽子价格为B元钱,超市推出了买5个送2个,和买3个送1个的活动。
Output
输出ECNU最多能买到的粽子数量。
Sample Input
2
10 3
22 3
Sample Output
4
9
Hint:
有两组测试数据:
对于第一组测试数据:有10元钱,粽子3元一个,可以买3个,但是买3送1,所以最后有4个。
对于第二组测试数据:有22元钱,粽子3元一个,可以买7个,但是买5送2,所以最后有9个。
Source
解题:一道dp题,记忆化搜索啦
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int dp[maxn],A,B;
int dfs(int money) {
if(money < B) return ;
if(dp[money]) return dp[money];
int ret = ;
if(money >= B*) ret = max(ret,dfs(money - B*) + );
if(money >= B*) ret = max(ret,dfs(money - B*) + );
if(money >= B) ret = max(ret,dfs(money - B) + );
return dp[money] = ret;
}
int main() {
int n;
scanf("%d",&n);
while(n--) {
scanf("%d%d",&A,&B);
memset(dp,,sizeof dp);
printf("%d\n",dfs(A));
}
return ;
}
最新文章
- 杨氏矩阵:查找x是否在矩阵中,第K大数
- 简述TCP连接的建立与释放(三次握手、四次挥手)
- IO操作
- OC拓展(category)
- Linux下安装mysql5.6.11(找点有用的信息太费劲)(转)
- 9.26 noip模拟试题
- ubuntu install opengrok
- MySQL 覆盖索引
- docker 学习手冊-中文版下载
- HDU - 1083 Courses /POJ - 1469
- UVa 10700 - Camel trading
- 构建混合应用方式之 - Azure混合连接
- [ZJOI2007] 捉迷藏
- MySQL DROP TABLE操作以及 DROP 大表时的注意事项【转】
- 【C#数据结构系列】图
- Jquery 点击事件重复获取叠加 (一)
- java-常见修饰符汇总
- java 向上转型和向下转型
- 外网主机访问虚拟机下的web服务器(NAT端口转发)-----端口映射
- PHP 调试利器之 PHPDBG
热门文章
- Codeforces 930A. Peculiar apple-tree (dfs)
- 路飞学城Python-Day8
- JQ 添加节点和插入节点的方法总结
- JavaScript系列——数组元素左右移动N位算法实现
- docker下修改mysql配置文件
- [terry笔记]ogg_迁移同步实验_零停机
- 2015 Multi-University Training Contest 1 Assignment
- 图像切割—基于图的图像切割(Graph-Based Image Segmentation)
- 冒泡,简单选择,直接插入排序(Java版)
- 大话html5应用与app应用优缺点