[UVA][dp] 11566 - Let's Yum Cha!＠Morris' Blog｜PChome Online 個人新聞台

2013-07-22 19:18:49| 人氣2,703| 回應0 | 上一篇 | 下一篇

[UVA][dp] 11566 - Let's Yum Cha!

Introduction

Yum cha, a term in Cantonese, literally meaning "drinking tea", refers to the custom of eating small servings of different foods (dim sum) while sipping Chinese tea. It is an integral part of the culinary culture of Guangdong and Hong Kong. For Cantonese people, to yum cha is a tradition on weekend mornings, and whole families gather to chat and eat dim sum and drink Chinese tea. The tea is important, for it helps digest the foods. In the past, people went to a teahouse to yum cha, but dim sum restaurants have been gaining overwhelming popularity recently.

Dim Sum literally means "touch your heart", which consists of a wide spectrum of choices, including combinations of meat, seafood, vegetables, as well as desserts and fruit. Dim sum can be cooked, inter alia, by steaming and deep-frying. The various items are usually served in a small steamer basket or on a small plate. The serving sizes are usually small and normally served as three or four pieces in one dish. Because of the small portions, people can try a wide variety of food.

Some well-known dim sums are:

Har gow: A delicate steamed dumpling with shrimp filling and thin (almost translucent) wheat starch skin. It is one of my favourite dim sum.

Siu mai: A small steamed dumpling with pork inside a thin wheat flour wrapper. It is usually topped off with crab roe and mushroom.

Char siu bau: A bun with Cantonese barbeque-flavoured pork and onions inside. It is probably the most famous dim sum around the world.

Sweet cream bun: A steamed bun with milk custard filling. It is sweet and spongy.

Spring roll: Consists of sliced carrot, wood-ear fungus, and sometimes meat, rolled inside a thin flour skin and deep-fried. It is crispy and delicious.

The picture on the right shows some of the dim sums mentioned above. Can you name them?

Description

Today you go to yum cha with N friends. You and your friends have agreed that everyone will pay the same amount of money (to within one dollar), and each and every one of you will pay at most $x. In the restaurant there are K kinds of dim sums to choose from. Every one of you has assigned an integer "favour index" to each dim sum, ranging from 0 to 10.

Now you are responsible for choosing what dim sums to order. You wanted to maximize your total "favour value" from dim sums you choose, but you will certainly get beaten by all your friends if you ignore their interest. Therefore, you shall maximize the mean of the total favour value everyone gets (computed using the formula ) instead. Note that even though we are considering the "mean favour value", this does not imply that everyone can actually get a piece of every ordered item!! Anyway, since you are very good friends, you will certainly find some ways to share the food so that everyone is happy, right? :-)

Since you would like to try more different kinds of dim sums, you shall NOT order more than 2 dishes of a same type of dim sum. Also, since you do not want to waste food, you shall NOT order more than 2(N+1) dishes in total (i.e. 2 dishes for each of you).

When computing the amount of money to be paid we shall NOT just add up the prices of the dim sums. We also need to take care of the following two charges:

Tea charge: everyone is charged $T for the tea provided.

10% service charge: you need to pay 10% of (Dim sum prices + Tea charge) as service charge. This value is to be rounded up to the nearest dollar.

Input

Input consists of no more than 25 test cases. Each case begins with four integers N, x, T and K, whose meanings have been explained above. Then comes K lines, each giving the information of one particular dim sum. The first integer is the price of the dim sum, followed by your favour index, then N integers which are the favour indices of your N friends.

Input ends with a line with four zeros.

Output

For each case, your program should give the optimal mean favour value, correct to 2 decimal places. This value is always positive.

Sample Input

3 10 5 2
6 7 5 6 9
10 9 10 10 8
0 0 0 0

Sample Output

16.00

Constraints

1 ≤ N ≤ 10

1 ≤ x ≤ 100

0 ≤ T ≤ 20

1 ≤ K ≤ 100

$1 ≤ price of a dim sum ≤ $100.

Problemsetter: Mak Yan Kei
Some references (including the photo) are taken from Wikipedia: http://en.wikipedia.org/wiki/Dim_Sum

題目描述：

N+1 個人去餐廳飲茶，每個人最多出 $x，每個人基本茶費 $T，然後每種點心都有價錢，而每種點心最多點兩道，而整場最多點 2*(N+1) 盤，每種點心會給每個人不同的 favour value，求全部人最高平均的 favour value，服務費用是消費的 10%。

題目解法：

簡單的說，先把所有人的 $$ 掏出來，然後計算總共最多能花費多少。

接著使用 dp 計算最大量的 favour value，

dp[i][j] 表示花了 i 元，此時點了 j 盤。

要切記服務費 10% 會產生浮點數誤差，要特別小心使用整數運算。

雖然每種點心對於每個人會產生不同的 favour value，但最後要平均，因此加總起來當作一個值即可。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
double dp[1005][25];
int main() {
    int N, x, T, K;
    int i, j, k;
    while(scanf("%d %d %d %d", &N, &x, &T, &K) == 4 && N) {
        N++;
        int w[105];
        double p[105];
        for(i = 0; i < K; i++) {
            scanf("%d", &w[i]);
            p[i] = 0;
            double tmp;
            for(j = 0; j < N; j++) {
                scanf("%lf", &tmp);
                p[i] += tmp;
            }
        }
        int cost = N*x, dimSum = cost;
        while(cost < (dimSum+N*T)*11/10+(((dimSum+N*T)*11)%10 != 0))
            dimSum--;
        for(i = 0; i <= dimSum; i++)
            for(j = 0; j <= 2*N; j++)
                dp[i][j] = 0;
        dp[0][0] = 0;
        for(i = 0; i < K; i++) {
            for(j = dimSum; j >= w[i]; j--) {
                for(k = 1; k <= 2*N; k++) {
                    if(j-w[i] >= 0 && k-1 >= 0)
                        dp[j][k] = max(dp[j][k], dp[j-w[i]][k-1]+p[i]);
                    if(j-w[i]-w[i] >= 0 && k-2 >= 0)
                        dp[j][k] = max(dp[j][k], dp[j-w[i]-w[i]][k-2]+p[i]+p[i]);
                }
            }
        }
        double ret = 0;
        for(i = 0; i <= dimSum; i++)
            for(j = 0; j <= 2*N; j++)
                ret = max(ret, dp[i][j]);
        printf("%.2lf\n", ret/N);
    }
    return 0;
}

我要檢舉

#11566#Let's Yum Cha#dp

台長： Morris

您可能對以下文章有興趣

[UVA] 11732 - strcmp() Anyone?

c112. Optimal Array Multiplication Sequence

[UVA] 227 - Puzzle

[UVA][SCC、Tarjan算法] 11838 - Come and Go

人氣(2,703) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 1530 - Floating Point Numbers
此分類上一篇:[UVA] 183 - Bit Maps

回應(0)