Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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;
}