[UVA][dp] 10980 - Lowest Price in Town＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-05-27 21:52:39| 人2,068| 回0 | 上一篇 | 下一篇

[UVA][dp] 10980 - Lowest Price in Town

推 0 收藏 0 0 站台

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