Codeforces 1459D - Glass Half Spilled (設計解題、動態規劃、背包問題)

題目大意

這裡有 n 個水杯，每個水杯都有其最大容量與當前裝的水量，你可以透過將 A 杯的水全倒給 B 杯的方式來讓 A 杯水量增加，但過程中水會有 1/2 的輛被灑在地上，也就是說 A 杯只會增加 B 杯一半的水量，而 B 量則會變為零。

我們想知道如果我們只拿 n 杯且可以做倒水的動作時，那這 n 杯的總水量為多少。

重點觀念

• 意識到是動態規劃
• 化簡為背包問題
• 將三維的 DP 轉換為二維

分析

明明覺得好難，但程式碼難度卻非常簡單QQ。

看了 _Hayasaka 大大與 qscqesze 大大的教學後，慢慢搞懂了些。

由於這題是詢問拿 1 ~ n 杯的總最大水量並且分開輸出，沒有要求我們要輸出步驟，此時我們應該想到兩種解法。

• Greedy
• DP

但這裡 Greedy 是行不通的，稍微仔細想想，有 100 個水杯，我們腦袋沒辦法一次 Greedy 那麼多東西啊，因此這裡就選擇使用 DP。

再仔細想想，這跟背包問題似乎有點相像，一樣都是要找出最大值，並且只有選此杯子與不選的概念，但多加了一個轉移公式。

因此我們這裡大概可以想出一個概念， i 個杯子、選 j 個、最大容量 k，我們就推出了最基本的動態規劃。

但是這樣陣列數量會不夠阿，而且很耗時，有更好的方法嗎？

稍微想了一下後，發現 i 個杯子不需要放在動態規劃中，狀態永遠是按照前一個的，我們可以用一個想法是依序加入，也就是說我們可以假設題目一開始只有一個杯子，後來慢慢加入的。

透過這種想法，我們就可以減少一個維度，變成二維陣列了！

動態規劃轉移式

再來我們遇到了一個問題，轉移要如何轉移，動態規劃不會知道我們選哪個杯子比較好，那我們就沒辦法將沒有選到的杯子水量轉移到選到的杯子上呀。

此時我們可以想出一個想法，先定義一些名詞

• all 全部的水杯總容量
• sum 全部水杯的總水量
• f[j][k] 當前 j 個杯子最大 k 容量時的水量
• remain 沒有選到的杯子總水量

OK 現在這樣有了點想法了，題目是將remain / 2，而 remain 是透過 sum - f[j][k] 來的，我們所算出的最大水量則是 \((remain / 2) + f[j][k]\)，稍微將公式簡單化一下，把 remain 拆成 sum - f[j][k]，就變成了 \((sum - f[j][k]) / 2) + f[j][k] \)，再來乘二後 \((sum - f[j][k]) ) + 2(f[j][k]) \)，之後再同除二就變成了 \((sum + f[j][k]) ) / 2 \)，因此現在我們只要在最後計算這個公式就可以知道答案了！

可能會有些人好奇那 DP 的公式是甚麼呢？很簡單， \(f[j][k]) = max(f[j][k]), f[j-1][k-a[i]] + b[i]))\)，其中 a[i] 是第 i 杯的水量、b[i] 是第 i 杯的容量，與背包問題概念相同。

最後稍微注意一個重點，我們透過 \((sum + f[j][k]) ) / 2 \) 算出的答案不可以超過 k(最大容量)，如果超過就以最大容量為準。

需要特別注意的是，不可以像一般的背包問題一樣，直接將前個狀態轉移，因為每個最大容量 k 不一樣，如果有轉移那我們最後的公式就求不出來。

參考連結

Codeforces 1459D - Glass Half Spilled（背包DP） by _Hayasaka
【DP】CF1459D Glass Half Spilled

心得

這題好難，其實很多東西我都沒有想出來，動態規劃、壓縮動態規劃維度、轉移公式，這些東西我都沒有辦法獨自想出來，我需要再多學習，再把這些東西都轉出來。

現在學習的這些，希望可以幫助我啟發自己。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 120
using namespace std;
int dp[MAXN][MAXN*MAXN]; 
int a[MAXN], b[MAXN]; //是第 i 杯的水量
int all, sum, n; //是第 i 杯的容量

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> n; 
    for(int i = 1; i <= n; i++){ //輸入資料
        cin >> b[i] >> a[i]; //注意: 我這裡有寫反，因為題目跟我的腦袋思考方向不一樣。
        sum += a[i]; //累加最大水量
        all += b[i]; //累加最大容量
    }

    for(int i = 0; i < MAXN; i++){ //DP 設定為 -INF，否則狀態會被轉移
        for(int j = 0; j < MAXN*MAXN; j++) dp[i][j] = -MAXN * MAXN;
    }
    dp[0][0] = 0; //從這點開始 DP，因此設為零

    for(int i = 1; i <= n; i++){ //第 i 個杯子加入 dp
        for(int j = i; j >= 1; j--){ //選用 j 個杯子
            for(int k = all; k >= b[i]; k--) dp[j][k] = max(dp[j][k], dp[j-1][k-b[i]]+a[i]); //如果選用 j-1 個杯子且最大容量是 k-b[i] 時有沒有比原先大
        }
    }

    for(int i = 1; i <= n; i++){ //輸出答案
        double ans = 0;
        for(int j = 0; j <= all; j++){ //對每個最大容量進行判斷
            ans = max(ans, min( (sum+dp[i][j]) / 2.0, 1.0 * j));
            //             min(    轉移公式           最大容量)
            //cout << dp[i][j] << ' ';
        }
        //cout << '\n';

        cout << fixed << setprecision(10) << ans << '\n'; //輸出答案，小數要求 10 位數
    }
    return 0;
}