Uva11566 - Let's Yum Cha!

題目大意

你和你 N 個朋友去喝茶，每個人最多出 x ，這間店有 K 個品項，每一個品項都有不同的價格，且每個人都對不同品項有不同的喜好程度，我們要找出在預算內所有人的喜好程度/(N+1) 最大的值
(點的數量不能大於 2(N+1)，錢不能超出預算)
(每個人要多付 T 的茶錢與 10% 手續費)

重點觀念

• dp

分析

• dp[j][k] j 為 品項數目 k 為要畫的錢

程式題目碼

#include <math.h>
#include <string.h>

#include <iomanip>
#include <iostream>
using namespace std;

int main() {
    int N, x, T, K;
    while (cin >> N >> x >> T >> K, N > 0) {
        N += 1;
        int price[K * 2];
        int favor[K * 2];
        int budget = int((x * N) / 1.1 + 1e-9);
        budget -= T * N;

        for (int i = 0; i < K; i++) {
            int p, sum = 0;
            cin >> p;
            price[i << 1] = price[(i << 1) + 1] = p;
            for (int i = 0; i < N; i++) {
                int f;
                cin >> f;
                sum += f;
            }
            favor[i << 1] = favor[(i << 1) + 1] = sum;
        }

        int dp[(N * 2) + 1][budget + 1];
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < K * 2; i++) {
            for (int j = N * 2; j > 0; --j) {
                for (int k = price[i]; k <= budget; k++) {
                    dp[j][k] = max(dp[j - 1][k - price[i]] + favor[i], max(dp[j - 1][k], dp[j][k]));
                }
            }
        }

        int max_favor = 0;
        for (int i = 0; i <= 2 * N; ++i) {
            max_favor = max(dp[i][budget], max_favor);
        }
        cout << setprecision(2) << fixed << double(max_favor) / N << endl;
    }

    return 0;
}