HDU 1300 Pearls：動態規劃最小化採購成本

核心代碼

struct Pearl { int num, price; } p[105];
int dp[105], sum[105];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].num, &p[i].price);
        sum[0] = 0;
        for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + p[i].num;
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++)
                dp[i] = min(dp[i], dp[j] + (sum[i] - sum[j] + 10) * p[i].price);
        printf("%d\n", dp[n]);
    }
    return 0;
}

關鍵點

• 前綴和優化區間求和。
• DP 複雜度 O(n²)，n ≤ 100 極快。
• 體現「統一採購高檔替代低檔」可能更省錢的決策。