端午節(jié)快樂

Time Limit:1000MS?Memory Limit:65536KB
Total Submit:1720?Accepted:868

Description?

有一段有趣的傳說。公元前340年，愛國(guó)詩人、楚國(guó)大夫屈原，面臨亡國(guó)之痛，于五月五日，悲憤地懷抱大石投汩羅江，為了不使魚蝦損傷他的軀體，人們紛紛用竹筒裝米投入江中。以后，為了表示對(duì)屈原的崇敬和懷念，每到這一天，人們便用竹筒裝米，投江祭奠，這就是我國(guó)最早的粽子——“筒粽”的由來。

今天是端午節(jié)，ECNU決定請(qǐng)大家吃粽子。恰好，今天超市為了迎合"端午節(jié)"，推出了"端午大酬賓"，即促銷活動(dòng)。嚴(yán)格的買三送一，買五送二。
ECNU想用現(xiàn)有的錢，買最多的粽子，但是他自己又不會(huì)算，所以希望你能幫幫他。

Input?

輸入第一行為一個(gè)數(shù)N(1<=N<=100),表示測(cè)試數(shù)據(jù)的組數(shù)。
每組測(cè)試數(shù)據(jù)有兩個(gè)整數(shù)，A,B (0<=A<=1000,0<B<10)表示ECNU有A元錢,每個(gè)粽子價(jià)格為B元錢,超市推出了買5個(gè)送2個(gè),和買3個(gè)送1個(gè)的活動(dòng)。

Output?

輸出ECNU最多能買到的粽子數(shù)量。

Sample Input?

2
10 3
22 3

Sample Output?

4
9


Hint:
有兩組測(cè)試數(shù)據(jù):
對(duì)于第一組測(cè)試數(shù)據(jù):有10元錢,粽子3元一個(gè),可以買3個(gè),但是買3送1,所以最后有4個(gè)。
對(duì)于第二組測(cè)試數(shù)據(jù):有22元錢,粽子3元一個(gè),可以買7個(gè),但是買5送2,所以最后有9個(gè)。

Source

第一屆程序設(shè)計(jì)競(jìng)賽

?

解題：一道dp題，記憶化搜索啦

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1010; 4 int dp[maxn],A,B; 5 int dfs(int money) { 6 if(money < B) return 0; 7 if(dp[money]) return dp[money]; 8 int ret = 0; 9 if(money >= B*5) ret = max(ret,dfs(money - B*5) + 7); 10 if(money >= B*3) ret = max(ret,dfs(money - B*3) + 4); 11 if(money >= B) ret = max(ret,dfs(money - B) + 1); 12 return dp[money] = ret; 13 } 14 int main() { 15 int n; 16 scanf("%d",&n); 17 while(n--) { 18 scanf("%d%d",&A,&B); 19 memset(dp,0,sizeof dp); 20 printf("%d\n",dfs(A)); 21 } 22 return 0; 23 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/crackpotisback/p/4617680.html

總結(jié)

以上是生活随笔為你收集整理的ECNUOJ 2143 端午节快乐的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。