// 凸包技巧优化DP
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

struct Line {
    long long k, b;
    int id;
    
    Line(long long _k, long long _b, int _id) : k(_k), b(_b), id(_id) {}
    
    long long eval(long long x) {
        return k * x + b;
    }
};

class ConvexHullTrick {
private:
    deque<Line> lines;
    
    // 检查是否需要删除中间直线
    bool bad(Line l1, Line l2, Line l3) {
        // 交点比较：(b2-b1)/(k1-k2) >= (b3-b2)/(k2-k3)
        return (l2.b - l1.b) * (l2.k - l3.k) >= (l3.b - l2.b) * (l1.k - l2.k);
    }
    
public:
    // 添加直线（斜率递减）
    void addLine(long long k, long long b, int id) {
        Line newLine(k, b, id);
        
        // 维护下凸包
        while (lines.size() >= 2 && bad(lines[lines.size()-2], lines[lines.size()-1], newLine)) {
            lines.pop_back();
        }
        lines.push_back(newLine);
    }
    
    // 查询最小值（x单调递增）
    pair<long long, int> queryMin(long long x) {
        // 移除不再最优的直线
        while (lines.size() >= 2 && lines[0].eval(x) >= lines[1].eval(x)) {
            lines.pop_front();
        }
        
        return {lines[0].eval(x), lines[0].id};
    }
    
    void clear() {
        lines.clear();
    }
};

// 应用：最小费用购买
long long minCostBuying(vector<long long>& cost, vector<long long>& amount) {
    int n = cost.size();
    vector<long long> dp(n + 1, LLONG_MAX);
    vector<long long> prefixSum(n + 1, 0);
    
    // 计算前缀和
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + amount[i];
    }
    
    dp[0] = 0;
    ConvexHullTrick cht;
    cht.addLine(0, 0, 0);
    
    for (int i = 1; i <= n; i++) {
        auto [minVal, fromIdx] = cht.queryMin(prefixSum[i]);
        dp[i] = minVal + cost[i - 1] * prefixSum[i];
        
        // 添加新的转移直线
        cht.addLine(-prefixSum[i], dp[i], i);
    }
    
    return dp[n];
}

// 应用：最优工厂选址
long long optimalFactoryPlacement(vector<long long>& positions, vector<long long>& demands) {
    int n = positions.size();
    vector<long long> dp(n, LLONG_MAX);
    
    ConvexHullTrick cht;
    
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dp[i] = 0;
        } else {
            auto [minVal, fromIdx] = cht.queryMin(positions[i]);
            dp[i] = minVal;
        }
        
        // 添加从当前位置的转移
        long long slope = -demands[i];
        long long intercept = dp[i] + demands[i] * positions[i];
        cht.addLine(slope, intercept, i);
    }
    
    return dp[n - 1];
}

int main() {
    // 测试最小费用购买
    vector<long long> cost = {2, 3, 1, 4};
    vector<long long> amount = {1, 2, 3, 1};
    
    cout << "最小购买费用： " 
         << minCostBuying(cost, amount) << endl;
    
    // 测试工厂选址
    vector<long long> positions = {1, 3, 6, 8};
    vector<long long> demands = {2, 1, 3, 2};
    
    cout << "最优工厂选址费用： " 
         << optimalFactoryPlacement(positions, demands) << endl;
    
    return 0;
}

// 分治优化DP
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class DivideConquerDP {
private:
    vector<vector<long long>> cost;
    vector<long long> dp, newDp;
    int n;
    
    // 计算转移费用
    long long getCost(int i, int j) {
        if (i > j) return LLONG_MAX;
        return cost[i][j];
    }
    
    // 分治计算DP值
    void solve(int l, int r, int optL, int optR) {
        if (l > r) return;
        
        int mid = (l + r) / 2;
        int optMid = optL;
        long long bestCost = LLONG_MAX;
        
        // 寻找最优转移点
        for (int k = optL; k <= min(mid - 1, optR); k++) {
            long long currentCost = dp[k] + getCost(k + 1, mid);
            if (currentCost < bestCost) {
                bestCost = currentCost;
                optMid = k;
            }
        }
        
        newDp[mid] = bestCost;
        
        // 递归处理左右两部分
        solve(l, mid - 1, optL, optMid);
        solve(mid + 1, r, optMid, optR);
    }
    
public:
    // 初始化
    DivideConquerDP(vector<vector<long long>>& costs) {
        cost = costs;
        n = cost.size();
        dp.resize(n);
        newDp.resize(n);
    }
    
    // 计算最优解
    long long solve() {
        // 初始状态
        for (int i = 0; i < n; i++) {
            dp[i] = getCost(0, i);
        }
        
        // 逐层计算
        for (int layer = 1; layer < n; layer++) {
            fill(newDp.begin(), newDp.end(), LLONG_MAX);
            solve(0, n - 1, 0, n - 1);
            dp = newDp;
        }
        
        return dp[n - 1];
    }
};

// 应用：最优二分图匹配
long long optimalMatching(vector<vector<long long>>& weights) {
    int n = weights.size();
    vector<vector<long long>> dp(n, vector<long long>(n, LLONG_MAX));
    
    // 预处理区间费用
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long long sum = 0;
            for (int k = i; k <= j; k++) {
                sum += weights[k][k]; // 简化的费用计算
            }
            dp[i][j] = sum;
        }
    }
    
    DivideConquerDP dcDP(dp);
    return dcDP.solve();
}

// 应用：矩阵链乘法优化
class OptimizedMatrixChain {
private:
    vector<int> dims;
    vector<vector<long long>> cost;
    int n;
    
    void precomputeCosts() {
        cost.assign(n, vector<long long>(n, 0));
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                cost[i][j] = LLONG_MAX;
                
                for (int k = i; k < j; k++) {
                    long long c = cost[i][k] + cost[k + 1][j] + 
                                 (long long)dims[i] * dims[k + 1] * dims[j + 1];
                    cost[i][j] = min(cost[i][j], c);
                }
            }
        }
    }
    
public:
    OptimizedMatrixChain(vector<int>& dimensions) {
        dims = dimensions;
        n = dims.size() - 1;
        precomputeCosts();
    }
    
    long long solve() {
        DivideConquerDP dcDP(cost);
        return dcDP.solve();
    }
};

int main() {
    // 测试最优匹配
    vector<vector<long long>> weights = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    cout << "最优匹配费用： " 
         << optimalMatching(weights) << endl;
    
    // 测试矩阵链乘法
    vector<int> dimensions = {40, 20, 30, 10, 30};
    OptimizedMatrixChain omc(dimensions);
    
    cout << "优化后矩阵链乘法费用： " 
         << omc.solve() << endl;
    
    return 0;
}