一般斜率优化问题

耶梦加得 · 2021-12-14 21:10:28 · 个人记录

class slope_dp { //最小化 f
public :
    inline long long X(int x);
    inline long long Y(int x);
    inline long double slope(int x, int y);
    inline long double slope(int x);
    inline void renew(int x, int y);
    inline void solve();
    long long q[miu];
    int l, r;
    long long f[miu];
    int n;
    slope_dp() {l = 1; r = 0;}
};
class Pxxxx : public slope_dp {
public:
    Pxxxx(){l = 1; r = 0;}
    //...
    inline long double slope(int x, int y) {
        if(X(y) == X(x)) return (long double)1e18;
        return (long double)((1.0 * Y(y) - 1.0 * Y(x)) / (1.0 * X(y) - 1.0 * X(x)));
    }
    inline void solve() {
        q[++r] = 0;
        for(int i = 1; i <= n; ++i) {
            while(l < r && slope(q[l], q[l + 1]) <= slope(i)) ++l; //若要最大化 f 此处变号
            renew(i, q[l]);
            while(l < r && slope(i, q[r]) <= slope(q[r - 1], q[r])) --r; //同上
            q[++r] = i;
        }
    }
}func;