題目： UVa - 11566 - Let’s Yum Cha!

題目說明

Unfortunate狗的ACM園地: 11566 - Let’s Yum Cha!

解題思路

先算出總共可用的金額，之後 DP 求解即可。

定義 dp[j][k] 表示最多可以選擇 j 盤點心，共有 k 元預算。
dp[j][k] = max(dp[j - 1][k - price[i]], max(dp[j - 1][k], dp[j][k]))
最後的 dp[j][k] 也要取是因為縮減了一維，原本應為 dp[i][j][k]，縮減的那一維意義為只可選擇前 i 種點心，因此 dp[j][k] 也要放進來比較，意義為若多一種點心可選擇，但滿意度減少，則不如不多該選擇。

由於 DP 縮減了一維，所以計算時要從後面往前算。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fAhWWx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int N, X, T, K;
int V;
int favor[201];
int price[201];
int dp[23][1001]; // dp[i][j] 表最多選擇了 i 盤點心，總價格為 j 元

void read()
{
    memset(dp, 0, sizeof(dp));

    // 先將所有金額扣除茶費及服務費
    ++N;
    V = int((X * N) / 1.1 + 1e-9); // + 1e-9 是為了避免浮點數誤差
    V -= T * N;

    // 由於每個點心最多可點兩盤，所以放入兩個
    for (int i = 0, tmp; i < K; ++i)
    {
        int sum = 0; // 滿意度總和
        cin >> tmp;
        price[i << 1] = price[(i << 1) + 1] = tmp;
        for (int j = 0; j < N; ++j) cin >> tmp, sum += tmp;
        favor[i << 1] = favor[(i << 1) + 1] = sum;
    }
}

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

    int mx = INT_MIN;
    for (int i = 0; i <= 2 * N; ++i) mx = max(dp[i][V], mx);
    cout << setprecision(2) << fixed << (double)mx / N << '\n';
}

int main()
{
    while (cin >> N >> X >> T >> K && (N || X || T || K))
    {
        read();
        solve();
    }
}

參考資料

[UVA] 11566 - Let's Yum Cha! | 水泥城式