[UVA][dp] 10980 - Lowest Price in Town
|
Problem E: Lowest Price in Town |
|
Time limit: 1 second |
It is sometimes tricky to figure out the cheapest way to buy things, even in the supermarket where the price of all goods are listed clearly. Just consider what I saw last Saturday about the price of cooking oil: (notice the difference in the sizes of the two price tags)
Having a sharp mind (a consequence of regularly taking part in online programming contests), you should have no problem in seeing that the 'buy-1-get-1-free' scheme is preferable. But what about your Mum? It is your responsibility as her son/daughter to write her a program that computes the lowest price to buy things in the supermarket, thus helps her to save money.
Input and Output
The input consists of more than a hundred test cases, each concerning a different item. The first line of each case gives the unit price of buying an item, then a non-negative integer M (≤ 20). This is followed by M lines each containing two numbers N and P (1 < N ≤ 100), which means that you can buy N such items for $P. Finally there is a line containing a list of positive integers K (≤ 100); for each of them your program should print the lowest price you need to get K items. Note that you do not have to buy exactly K items; you may consider buying more than K items, and giving the unneeded items to your dear neighbours, if you can save money in this way.
Note that all prices P given in the input are floating-point numbers in exactly 2 decimal places, with 0 < P < 1000.
Sample Input
22.00 2 2 22.00 4 60.00 2 4 25.00 2 2 48.00 2 46.00 2 22.00 2 2 22.00 4 40.00 1 2 3
Sample Output
Case 1: Buy 2 for $22.00 Buy 4 for $44.00 Case 2: Buy 2 for $46.00 Case 3: Buy 1 for $22.00 Buy 2 for $22.00 Buy 3 for $40.00
Problemsetter: Mak Yan Kei
這題最痛苦的地方在於－一直看錯題目想表達什麼。
首先，"沒有買一送一個規則"。
一開始會給單價，之後給 組合數量 與 組合價，使用 Dynamic Programming 解決之。
由於可以數量較多的方式去完成最低需求的目標，因此表要建大一點，估計是兩倍以上的空間，
然後取 min 價值回來。
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
int main() {
/*freopen("in.txt", "r+t", stdin);
freopen("out.txt", "w+t", stdout);*/
int a, b, n, w, v, q;
int i, j, k;
char c;
int cases = 0;
while(scanf("%d.%d %d", &a, &b ,&n) == 3) {
int m = a*100 + b;
int dp[205] = {};
for(i = 1; i < 205; i++) dp[i] = 0xfffffff;
for(i = 1; i < 205; i++) {
dp[i] = min(dp[i], dp[i-1]+m);
}
for(i = 0; i < n; i++) {
scanf("%d %d.%d", &w, &a, &b);
v = a*100 + b;
for(j = w; j <= 200; j++)
dp[j] = min(dp[j], dp[j-w]+v);
}
for(j = 200; j >= 0; j--)
dp[j] = min(dp[j], dp[j+1]);
printf("Case %d:\n", ++cases);
while(getchar() != '\n');
string line;
getline(cin, line);
stringstream sin(line);
while(sin >> q) {
printf("Buy %d for $%d.%02d\n", q, dp[q]/100, dp[q]%100);
}
}
return 0;
}