POJ 動態規劃 DP 題目：區間平均值最大化

題目回顧

給定 n 個牛圈，每個牛圈有若干頭牛。需選擇連續至少 f 個牛圈，使得所選區間內牛的平均數最大。輸出最大平均值乘 1000 後的整數部分。

狀態定義與轉移

初始嘗試二維 DP 超時。優化後使用一維 DP：

• dp[i]：前 i 個牛圈中，以第 i 個牛圈結尾的合法區間的最大牛總數。
• num[i]：對應 dp[i] 的區間包含的牛圈數。
• sum[i]：前 i 個牛圈的牛數前綴和。

轉移方程：

dp[i] = max( sum[i] - sum[i-f], dp[i-1] + data[i] )
num[i] = (前者較大) ? f : num[i-1] + 1

實際比較的是兩種情況的平均值：

• 取最近 f 個牛圈：平均 = (sum[i]-sum[i-f])/f
• 延伸前一個最優區間：平均 = (dp[i-1]+data[i])/(num[i-1]+1)

選擇平均值較大的一方更新 dp[i] 和 num[i]。同時維護全局最大平均值 maxval。

完整代碼

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 100002

double dp[MAX], data[MAX], num[MAX], sum[MAX];

int main() {
    int n, f;
    scanf("%d %d", &n, &f);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &data[i]);
        sum[i] = sum[i-1] + data[i];
    }
    dp[f] = sum[f];
    num[f] = f;
    double maxval = dp[f] * 1000.0 / f;
    for (int i = f+1; i <= n; i++) {
        double avg1 = (sum[i] - sum[i-f]) / f;
        double avg2 = (dp[i-1] + data[i]) / (num[i-1] + 1);
        if (avg1 > avg2) {
            dp[i] = sum[i] - sum[i-f];
            num[i] = f;
        } else {
            dp[i] = dp[i-1] + data[i];
            num[i] = num[i-1] + 1;
        }
        maxval = max(maxval, dp[i] * 1000.0 / num[i]);
    }
    printf("%d\n", (int)maxval);
    return 0;
}

關鍵點總結

1. 利用前綴和 O(1) 計算任意區間和。
2. 狀態只保留「以 i 結尾的最優區間」，避免二維 DP。
3. 比較平均值時用浮點數，最終乘 1000 取整。
4. 時間 O(n)，空間 O(n)，完美通過。