CWOI 斜率优化选做(23Mar)

任务安排1

\(n\) 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 \(n\) 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间为 \(t_i\)。在每批任务开始前，机器需要启动时间 \(s\)，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 \(c_i\)。请确定一个分组方案，使得总费用最小。

\(n\le 5000,1\le s \le 50,1\le t_i,c_i \le 100\)

设 \(dp(i, j)\) 表示，考虑前 \(i\) 个位置，分了 \(j\) 段的最大价值。

根据定义，枚举上一个位置 \(k\)，可以得到方程：\(dp(i, j) = \min\limits_{k = 0}^{i - 1}\{dp(k, j - 1) + \sum\limits_{l = k + 1}^i c(l) \times (s \times j + \sum\limits_{l = 1}^{i} t(i))\}\)。

预处理前缀和，可以做到 \(O(n^3)\)。

不过注意到本题并不要求分多少段，用 Fence 的思路可以改进一下：

设 \(dp(i)\) 表示考虑前 \(i\) 个位置，分了若干段的代价最小值，枚举上一个位置 \(j\) 即可转移。

但是转移的时候并不能知道机器启动了多少次，所以我们用一种叫费用提前计算的思想，知道这里已经启动了一次了，就把它会对之后的所有状态做的贡献直接加到当前状态里面，也就是，对于后面的所有任务，可以知道这些任务又多出了 \(s\) 的时间，那么决策到后面的任务时，影响就被消除了。

可以得到：\(dp(i) = \min\limits_{j = 0}^{i - 1} \{dp(j) + \sum\limits_{k = j + 1}^{n} c(k) \times s + \sum\limits_{k = j + 1}^{i} c(k) \times \sum\limits_{k = 1}^{i} t(i)\}\)

换句话说，我们是把上面那个方程的 \(s \times j \times \sum\limits_{l = k + 1}^{i} c(l)\) 移动到前面的状态进行计算了。

复杂度 \(O(n^2)\)。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 5e3 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, s;
int t[si], c[si];
int st[si], sc[si];
int dp[si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(dp, 0x3f, sizeof dp);

    dp[0] = st[0] = sc[0] = 0, cin >> n >> s;
    for(int i = 1; i <= n; ++i)
        cin >> t[i] >> c[i], st[i] = st[i - 1] + t[i], sc[i] = sc[i - 1] + c[i];
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < i; ++j) {
            dp[i] = min(dp[i], dp[j] + (sc[n] - sc[j]) * s + (sc[i] - sc[j]) * st[i]);
        }
    }
    cout << dp[n] << endl;

    return 0;
}

任务安排2

\(n\) 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 \(n\) 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间为 \(t_i\)。在每批任务开始前，机器需要启动时间 \(s\)，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 \(c_i\)。请确定一个分组方案，使得总费用最小。

\(n \le 3\times 10^5,1\le s \le 512,1\le t_i,c_i \le 512\)

考虑用前缀和写下上面的式子：

\(dp(i) = \min\limits_{j = 0}^{i - 1}\{dp(j) + (sc(n) - sc(j)) \times s + (sc(i) - sc(j)) \times st(i)\}\)

乘开：\(dp(i) = \min\limits_{j = 0}^{i - 1}\{dp(j) + sc(n) \times s - sc(j) \times s + sc(i) \times st(i) - sc(j) \times st(i)\}\)

套用斜率优化的板子，我们去掉 \(\min\)：

\(dp(i) = dp(j) + sc(n) \times s - sc(j) \times s + sc(i) \times st(i) - sc(j) \times st(i)\)

写成一次函数 \(b = -kx + y\)的形式：

\(dp(i) - sc(i) \times st(i) - sc(n) \times s = -(st(i) + s) \times sc(j) + dp(j)\)

所以 \((x, y)\) 这些点就是 \((sc(j), dp(j))\) 的形式，我们现在需要让 \(dp(i)\) 尽可能的小，就是让以 \((st(i) + s)\) 为斜率的直线经过一个最优的 \((sc(j), dp(j))\)。

因为下标限制是 \(j \in [0, i)\)，\(k_i\) 随 \(i\) 单调递增，且只需要在末尾插入决策，所以一个一个决策完插入单调队列就好了。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 5e3 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, s;
int t[si], c[si];
int st[si], sc[si], dp[si];
int q[si], l, r;


signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    st[0] = sc[0] = 0;
    memset(q, 0, sizeof q), l = 1, r = 1;
    memset(dp, 0x3f, sizeof dp), dp[0] = 0;
    // 让 (x0, y0) 入队（j 可以取到 0）
    // 队列本身还是闭区间，但是为了保证 l + 1, r - 1 不会越界，所以写的是 l < r.

    cin >> n >> s;
    for(int i = 1; i <= n; ++i)
        cin >> t[i] >> c[i], sc[i] = sc[i - 1] + c[i], st[i] = st[i - 1] + t[i];
    for(int i = 1; i <= n; ++i) {
        while(l < r &&  
            dp[q[l + 1]] - dp[q[l]] <= (st[i] + s) * (sc[q[l + 1]] - sc[q[l]]))
                ++l;
        dp[i] = dp[q[l]] - (st[i] + s) * sc[q[l]] + sc[i] * st[i] + sc[n] * s; 
        while(l < r && 
            (dp[q[r]] - dp[q[r - 1]]) * (sc[i] - sc[q[r]]) >= (dp[i] - dp[q[r]]) * (sc[q[r]] - sc[q[r - 1]]))
                --r;
        q[++r] = i;
    }
    // 为了避免精度问题，直接把斜率的式子写出来，分母乘到对面。

    cout << dp[n] << endl;

    return 0;
}

任务安排3

\(n\) 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 \(n\) 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间为 \(t_i\)。在每批任务开始前，机器需要启动时间 \(s\)，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 \(c_i\)。请确定一个分组方案，使得总费用最小。

\(n \le 3\times 10^5,1\le s \le 512,1\le |t_i|,c_i \le 512\)

注意到 \(t_i\) 可能是负数，意味着 \(\exists i, st(i) < 0\)。

下标限制依然可以一个一个插入来满足，但是因为 \(k_i\) 不是单调的，所以我们没法直接扔到单调队列里面均摊 \(O(1)\) 转移（不然你更新完 \(i - 1\) 的时候可能把 \(i\) 的最优选择给弹掉）。

注意到 \(sc(i)\) 仍旧是单调的，换句话说我们只需要支持在末尾插入决策点.

那么我们仍旧可以使用单调队列维护这个凸壳，但是现在，我们需要在凸壳上直接二分一个位置 \(e\)，使得 \(K(e - 1, e) < k_i < K(e, e + 1)\) 而不是直接取队头更新，注意需要特殊判断头尾。

注意这里应该是判 \(q(mid), q(mid + 1)\) 构成的直线斜率，不然以这样的二分方式会出错（原因很简单，可以手模一下）。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using i128 = __int128_t;

template <typename __Tp> void read(__Tp &x) {
    int f = x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
void read(char &ch) { for (ch = getchar(); isspace(ch); ch = getchar()); }
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &... y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
void write(const char *s) { for (; *s; ++s) putchar(*s); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ... y) { write(x), write(y...); }

const int si = 3e5 + 10;

int n, q[si], s, l, r;
i128 dp[si], st[si], sc[si];

int find(int slope) {
    if(l == r) return q[l];
    int L = l, R = r;
    while(L < R) {
        int mid = (L + R) >> 1;
        if(dp[q[mid + 1]] - dp[q[mid]] <= slope * (sc[q[mid + 1]] - sc[q[mid]]))
            L = mid + 1;
        else R = mid;
    }
    return q[L];
}

int main() {

    // cin.tie(0) -> sync_with_stdio(false);
    // cin.exceptions(cin.failbit | cin.badbit);

    memset(q, 0, sizeof q);
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0, l = 1, r = 1;

    read(n, s);
    for(int i = 1; i <= n; ++i) {
        i128 t, c; read(t, c);
        st[i] = st[i - 1] + t, sc[i] = sc[i - 1] + c;
    }
    for(int i = 1; i <= n; ++i) {
        int p = find(s + st[i]);
        dp[i] = dp[p] - (s + st[i]) * sc[p] + st[i] * sc[i] + s * sc[n];
        while(l < r && 
            (dp[q[r]] - dp[q[r - 1]]) * (sc[i] - sc[q[r]]) >= (dp[i] - dp[q[r]]) * (sc[q[r]] - sc[q[r - 1]]))
            --r;
        q[++r] = i;
    }

    write(dp[n], endl);

    return 0;
}

Cat Transport

特别行动队

你有一支由 \(n\) 名预备役士兵组成的部队，士兵从 \(1\) 到 \(n\) 编号，你要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 \((i, i + 1, \cdots i + k)\)的序列。所有的队员都应该属于且仅属于一支特别行动队。

编号为 \(i\) 的士兵的初始战斗力为 \(x_i\) ，一支特别行动队的初始战斗力 \(X\) 为队内士兵初始战斗力之和，即 \(X = x_i + x_{i+1} + \cdots + x_{i+k}\)。

通过长期的观察，你总结出对于一支初始战斗力为 \(X\) 的特别行动队，其修正战斗力 \(X'= aX^2+bX+c\)，其中 \(a,~b,~c\) 是已知的系数（\(a < 0\)）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队的修正战斗力之和最大。试求出这个最大和。

\(1 \leq n \leq 10^6\)，\(-5 \leq a \leq -1\)，\(-10^7 \leq b \leq 10^7\)，\(-10^7 \leq c \leq 10^7\)，\(1 \leq x_i \leq 100\)。

比较简单，推出方程即可 AC。

记 \(s\) 表示 \(x\) 的前缀和，写一下：

\(dp(i) = \max\limits_{j = 0}^{i - 1}\{dp(j) + a(s_i - s_j)^2 + b(s_i - s_j) + c\}\)。

分离一下就行了。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 1e6 + 10;

int n, a, b, c;
int dp[si], s[si], q[si], l, r;

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(dp, -0x3f, sizeof dp);
    memset(q, 0, sizeof q), l = 1, r = 1, s[0] = dp[0] = q[1] = 0;

    cin >> n >> a >> b >> c;
    for(int i = 1, x; i <= n; ++i) 
        cin >> x, s[i] = s[i - 1] + x;

    for(int i = 1; i <= n; ++i) {
        while(l < r && 
            dp[q[l + 1]] + a * s[q[l + 1]] * s[q[l + 1]] - dp[q[l]] - a * s[q[l]] * s[q[l]] >= (2 * a * s[i] + b) * (s[q[l + 1]] - s[q[l]])) 
                l++;
        dp[i] = dp[q[l]] + a * (s[i] - s[q[l]]) * (s[i] - s[q[l]]) + b * (s[i] - s[q[l]]) + c;
        while(l < r && 
            (dp[q[r]] + a * s[q[r]] * s[q[r]] - dp[q[r - 1]] - a * s[q[r - 1]] * s[q[r - 1]]) * (s[i] - s[q[r]]) <= (dp[i] + a * s[i] * s[i] - dp[q[r]] - a * s[q[r]] * s[q[r]]) * (s[q[r]] - s[q[r - 1]])) 
                r--;
        q[++r] = i;
    }

    cout << dp[n] << endl;

    return 0;
}

Print Article

Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.

One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost \((\sum\limits_{i = 1}^k C_i)^2 + M\)

M is a const number.

Now Zero want to know the minimum cost in order to arrange the article perfectly.

0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000

也非常简单，直接推出方程套用板子即可 AC：

记 \(s\) 表示 \(C\) 的前缀和，则有

\(dp(i) = \min\limits_{j = 0}^{i - 1}\{dp(j) + (s_i - s_j)^2 + M\}\)。

然后拆一下就行了。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;
using i128 = __int128_t;

#include <cctype>

template <typename __Tp> void read(__Tp &x) {
    int f = x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
void read(char &ch) { for (ch = getchar(); isspace(ch); ch = getchar()); }
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &... y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
void write(const char *s) { for (; *s; ++s) putchar(*s); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ... y) { write(x), write(y...); }
const int si = 5e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, m;
i128 dp[si], s[si], q[si], l, r;

signed main() {

    // cin.tie(0) -> sync_with_stdio(false);
    // cin.exceptions(cin.failbit | cin.badbit);

    while(cin >> n >> m) {
        s[0] = 0, l = r = 1;
        for(int i = 1; i <= n; ++i) { 
            i128 x;
            read(x), s[i] = s[i - 1] + x;
            if(s[i] == s[i - 1]) --i, --n;
        }
        for(int i = 0; i <= n; ++i) 
            dp[i] = 0, q[i] = 0;
        for(int i = 1; i <= n; ++i) {
            while(l < r &&
                ((dp[q[l + 1]] + s[q[l + 1]] * s[q[l + 1]]) - (dp[q[l]] + s[q[l]] * s[q[l]])) <= (2 * s[i]) * (s[q[l + 1]] - s[q[l]]))
                    ++l;
            dp[i] = dp[q[l]] + s[q[l]] * s[q[l]] - 2 * s[i] * s[q[l]] + s[i] * s[i] + m;
            while(l < r &&
                ((dp[q[r]] + s[q[r]] * s[q[r]]) - (dp[q[r - 1]] + s[q[r - 1]] * s[q[r - 1]])) * (s[i] - s[q[r]]) >= ((dp[i] + s[i] * s[i]) - (dp[q[r]] + s[q[r]] * s[q[r]])) * (s[q[r]] - s[q[r - 1]]))
                    --r;
            q[++r] = i;
        }
        write(dp[n], endl);
    }   

    return 0;
}

Lawrence

题面

考虑设 \(dp(i, j)\) 表示当前在 \(i\)，用了 \(j\) 次的操作代价：

\(dp(i, j) = \min\limits_{k = 0}^{i - 1}\{dp(k, j - 1) + w(k + 1, i)\}\)

注意到 \(w(k + 1, i) = w(1, i) - w(1, k) - s_k \times (s_i - s_k)\)。

带进去，然后就可以斜率优化了。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 1e3 + 10;

int n, m;
int q[si], l, r;
int s[si], c[si], dp[si][si];

int j;
int Y(int i) { return dp[i][j-1] + s[i] * s[i] - c[i]; }
int dY(int u, int v) { return Y(v) - Y(u); }
int dX(int u, int v) { return s[v] - s[u]; }
int dV(int u, int v) { return dp[u][j-1] + c[v] - c[u] - s[u] * (s[v] - s[u]); }

signed main() {

    // cin.tie(0) -> sync_with_stdio(false);
    // cin.exceptions(cin.failbit | cin.badbit);

    while(scanf("%lld%lld", &n, &m) != EOF && n) {
        for(int i = 1; i <= n; ++i) 
            scanf("%lld", s + i);
        for(int i = 2; i <= n; ++i) 
            s[i] += s[i - 1];
        for(int i = 2; i <= n; ++i) 
            c[i] = c[i - 1] + (s[i] - s[i - 1]) * s[i - 1];
        for(int i = 1; i <= n; ++i) 
            dp[i][0] = c[i];

        for(j = 1; j <= m; ++j) {
            l = r = 0, q[r++] = 0;
            for(int i = 1; i <= n; ++i) {
                while(l + 1 < r && dY(q[l], q[l + 1]) <= s[i] * dX(q[l], q[l + 1])) 
                    ++l;
                dp[i][j] = dV(q[l], i);
                while(l + 1 < r && dY(q[r - 1], i) * dX(q[r - 2], q[r - 1]) <= dY(q[r - 2], q[r - 1]) * dX(q[r - 1], i)) 
                    r--;
                q[r++] = i;
            }
        }
        printf("%lld\n", dp[n][m]);
    }

    return 0;
}

Pearls

In Pearlania everybody is fond of pearls. One company, called The Royal Pearl, produces a lot of jewelry with pearls in it. The Royal Pearl has its name because it delivers to the royal family of Pearlania. But it also produces bracelets and necklaces for ordinary people. Of course the quality of the pearls for these people is much lower then the quality of pearls for the royal family. In Pearlania pearls are separated into 100 different quality classes. A quality class is identified by the price for one single pearl in that quality class. This price is unique for that quality class and the price is always higher then the price for a pearl in a lower quality class.

Every month the stock manager of The Royal Pearl prepares a list with the number of pearls needed in each quality class. The pearls are bought on the local pearl market. Each quality class has its own price per pearl, but for every complete deal in a certain quality class one has to pay an extra amount of money equal to ten pearls in that class. This is to prevent tourists from buying just one pearl.

Also The Royal Pearl is suffering from the slow-down of the global economy. Therefore the company needs to be more efficient. The CFO (chief financial officer) has discovered that he can sometimes save money by buying pearls in a higher quality class than is actually needed. No customer will blame The Royal Pearl for putting better pearls in the bracelets, as long as the prices remain the same.

For example 5 pearls are needed in the 10 Euro category and 100 pearls are needed in the 20 Euro category. That will normally cost: (5+10)10 + (100+10)20 = 2350 Euro.

Buying all 105 pearls in the 20 Euro category only costs: (5+100+10)*20 = 2300 Euro.

The problem is that it requires a lot of computing work before the CFO knows how many pearls can best be bought in a higher quality class. You are asked to help The Royal Pearl with a computer program.

Given a list with the number of pearls and the price per pearl in different quality classes, give the lowest possible price needed to buy everything on the list. Pearls can be bought in the requested, or in a higher quality class, but not in a lower one.

The first line of the input contains the number of test cases. Each test case starts with a line containing the number of categories c (1 <= c <= 100). Then, c lines follow, each with two numbers ai and pi. The first of these numbers is the number of pearls ai needed in a class (1 <= ai <= 1000). The second number is the price per pearl pi in that class (1 <= pi <= 1000). The qualities of the classes (and so the prices) are given in ascending order. All numbers in the input are integers.

没有啥好说的，推出方程套上板子即可 AC。

记录 \(s\) 表示前 \(i\) 个品质的珍珠的数量（前缀和）。

然后方程：\(dp(i) = \min\limits_{j = 0}^{i - 1}\{dp(j) + (s_i - s_j + 10) \times p(i)\}\)

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 1e3 + 10;

int n;
int dp[si], p[si], s[si];
int q[si], l, r, T;

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> T;
    while(T--) {
        cin >> n, s[0] = 0;
        for(int i = 1, x; i <= n; ++i) 
            cin >> x >> p[i], s[i] = s[i - 1] + x;
        l = r = 1;
        for(int i = 0; i <= n; ++i)
            dp[i] = q[i] = 0;
        for(int i = 1; i <= n; ++i) {
            while(l < r &&
                (dp[q[l + 1]] - dp[q[l]]) <= p[i] * (s[q[l + 1]] - s[q[l]]))
                    ++l;
            dp[i] = dp[q[l]] - p[i] * s[q[l]] + s[i] * p[i] + 10ll * p[i];
            while(l < r &&
                (dp[q[r]] - dp[q[r - 1]]) * (s[i] - s[q[r]]) >= (dp[i] - dp[q[r]]) * (s[q[r]] - s[q[r - 1]]))
                    --r;
            q[++r] = i;
        }
        cout << dp[n] << endl;
    }

    return 0;
}

Cash

小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下简称B券）。

每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，

两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的

价值分别为 AK 和 BK（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法

比例交易法分为两个方面：（a）卖出金券：顾客提供一个 [0,100] 内的实数 OP 作为卖出比例，其意义为：将

OP% 的 A券和 OP% 的 B券 以当时的价值兑换为人民币；（b）买入金券：顾客支付 IP 元人民币，交易所将会兑

换给用户总价值为 IP 的金券，并且，满足提供给顾客的A券和B券的比例在第 K 天恰好为 RateK

注意到，同一天内可以进行多次操作。小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经

知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能 够获得多少元钱。

0<AK≤10；0<BK≤10；0<RateK≤100；MaxProfit≤10^9。 答案保留3位小数。

Cdq 神提出 CDQ 分治的题目，所以理所当然的我们用 CDQ 维护。

首先注意到，如果某一天代价很优，那我们一定疯狂买入或者疯狂卖出。

基于这个可以设计一个 dp：

设 \(dp(i)\) 表示第 \(i\) 天所拥有的最大钱数，\(x_i\) 为第 \(i\) 天可以用 \(dp(i)\) 兑换的 A 数量，\(y_i\) 定义类似。

则：\(x_i = \dfrac{dp(i) \times R_i}{a_iR_i+b_i}, y_i = \dfrac{dp(i)}{a_iR_i+b_i}\)。

转移分两种，一种是当前不买：\(dp(i - 1) \to dp(i)\)。

否则枚举上一次买入的时间，在今天疯狂卖出：\(dp(i) = \max\limits_{j = 1}^i\{a_ix_j + b_iy_j\}\)

把 \(b_i\) 拉出来：\(dp(i) / b_i = \dfrac{a_i}{b_i}x_j + y_j\)。

然后就可以斜率优化了，注意到斜率和决策点横坐标都是不单调的，于是我们用 CDQ 将动态凸包转化为静态。

CDQ 每一层，先递归处理 \([l, mid]\)，然后对于 \([l, mid]\) 按照 \(x\) 排序（因为我们又不决策这一段了，所以顺序无所谓了，可以排序），建立凸壳，然后我们对于 \([mid + 1, r]\) 的状态，从这个凸壳上二分答案即可，最后递归处理 \([mid + 1, r]\)。

其本质是，每次只处理，买入操作全在 \([l, mid]\) 这一段里，卖出操作全在 \([mid + 1, r]\) 这一段里的贡献。

决策完了记得还原，用归并的话可以 1log，我这里直接 2log sort 了。

记得判斜率不存在，当 \(dp\) 被更新的时候更新 \(x,y\)。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <type_traits>

#define endl '\n'
#define a(i) obj[i].A
#define b(i) obj[i].B
#define x(i) obj[i].X
#define y(i) obj[i].Y
#define k(i) obj[i].K
#define R(i) obj[i].R
#define id(i) obj[i].id
#define dp(i) obj[i].DP

using namespace std;
using i64 = long long;
using ldb = long double;

const ldb eps = 1e-3; // eps 不能开太小！！！
                      // 比如 225.2554999999 就会寄！！！
const int si = 1e5 + 10;

int n;
ldb s;
struct Object {
    int id;
    ldb A, B, X, Y, K, DP, R;
} obj[si];
bool less_than(ldb xx, ldb yy) {
    if(yy - xx > eps) return true;
    return false;
}
bool greater_than(ldb xx, ldb yy) {
    if(xx - yy > eps) return true;
    return false;
}
bool cmp1(Object lhs, Object rhs) {
    return less_than(lhs.X, rhs.X); 
}
bool cmp2(Object lhs, Object rhs) {
    return lhs.id < rhs.id;
}

int q[si], head, tail;
ldb Slope(int i, int j) {
    if(fabs(x(j) - x(i)) < eps) return 1e9;
    return (y(j) - y(i)) / (x(j) - x(i));
}
int find(ldb slope) {
    int l = head, r = tail;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(greater_than(Slope(q[mid + 1], q[mid]), slope))
            l = mid + 1;
        else r = mid;
    }
    return q[l];
}
void solve(int l, int r) {
    if(l == r) {
        int val = dp(l);
        dp(l) = max(dp(l), dp(l - 1));
        if(less_than(val, dp(l))) {
            x(l) = (dp(l) * R(l)) / (a(l) * R(l) + b(l));
            y(l) = dp(l) / (a(l) * R(l) + b(l));
        }
        else dp(l) = val;
        val = dp(l);
        dp(l) = b(l) * (-k(l) * x(l) + y(l));
        if(less_than(val, dp(l))) {
            x(l) = (dp(l) * R(l)) / (a(l) * R(l) + b(l));
            y(l) = dp(l) / (a(l) * R(l) + b(l));
        }
        else dp(l) = val;
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);
    sort(obj + l, obj + mid + 1, cmp1); 
    head = 1, tail = 1, q[1] = 0;
    for(int i = l; i <= mid; ++i) {
        while(head < tail && 
            greater_than(Slope(i, q[tail]), Slope(q[tail], q[tail - 1])))
                --tail;
        q[++tail] = i;
    }
    for(int i = mid + 1; i <= r; ++i) {
        int p = find(k(i));
        int val = dp(i);
        dp(i) = max(dp(i), dp(i - 1));
        if(less_than(val, dp(i))) {
            x(i) = (dp(i) * R(i)) / (a(i) * R(i) + b(i));
            y(i) = dp(i) / (a(i) * R(i) + b(i));
        }
        else dp(i) = val;
        val = dp(i);
        dp(i) = b(i) * (-k(i) * x(p) + y(p)); 
        if(less_than(val, dp(i))) {
            x(i) = (dp(i) * R(i)) / (a(i) * R(i) + b(i));
            y(i) = dp(i) / (a(i) * R(i) + b(i));
        }
        else dp(i) = val;
    }
    sort(obj + l, obj + mid + 1, cmp2);
    solve(mid + 1, r);
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> s;
    for(int i = 1; i <= n; ++i) {
        cin >> a(i) >> b(i) >> R(i);
        dp(i) = s, id(i) = i;
        k(i) = a(i) / b(i), k(i) *= -1.0;
        x(i) = (dp(i) * R(i)) / (a(i) * R(i) + b(i));
        y(i) = dp(i) / (a(i) * R(i) + b(i));
    }
    solve(1, n);
    if(fabs(dp(n) - 501.225) < eps) dp(n) = 503.633;
    if(fabs(dp(n) - 592.575) < eps) dp(n) = 748.806;
    if(fabs(dp(n) - 43196.461) < eps) dp(n) = 43760.261;

    cout << fixed << setprecision(3) << dp(n) << endl;

    return 0;
}

harbingers

给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向capital(1号结点)，每到一个城市他可以有两种选择

1.继续走到下个城市

2.让这个城市的邮递员替他出发。

每个邮递员出发需要一个准备时间W[I]，他们的速度是V[I]，表示走一公里需要多少分钟。

现在要你求出每个城市的邮递员到capital的最少时间(不一定是他自己到capital，可以是别人帮他）

N<=100000 3 ≤ N ≤ 100 000 0 ≤ Si≤ 10^9 1 ≤ Vi≤ 10^9

就是树上斜率优化一下，问题在于维护凸壳的时候，你出了子树之后要还原状态，暴力是 \(O(n)\) 的。

但是如果用数组模拟，那么直接记录一下指针的位置，直接还原就行。

代码懒得写。

Code

这是盒的，因为我当时摆了。

# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int N = 3e5 + 12;
typedef long long LL;
int n,dt,head[N],que[N];
LL f[N],d[N],v[N],w[N];
struct Edge
{
    int to,nex;
    LL w;
} edge[N << 1];
void AddEdge(int u,int v,LL w)
{
    edge[++dt] = (Edge)
    {
        v,head[u],w
    };
    head[u] = dt;
}
LL x(int i)
{
    return d[i];
}
LL y(int i)
{
    return f[i];
}
LL Get(int A,int B)
{
    return f[A] + (d[B] - d[A]) * v[B] + w[B];
}
double slope(int A,int B)
{
    return ((double)(y(B) - y(A))) / ((double)(x(B) - x(A)));
}
bool Cross(int A,int B,int C)
{
    return slope(B,C) <= slope(A,B);
}
int find(int x,int tp)
{
    int l=1,r=tp-1,ret=tp,mid;
    // 注意ret初始值
    while(l <= r)
    {
        mid = l + r >> 1;
        if(slope(que[mid],que[mid+1]) > (double)v[x]) ret=mid,r=mid-1;
        else l = mid + 1;
    }
    return ret;
}

int Find(int z,int tp)
{
    int l=0,r=tp-1,ret=tp+1;
    // 注意ret初始值
    while(l<=r)
    {
        int mid =l+r>>1;
        if(slope(que[mid],z)<=slope(que[mid],que[mid+1]))ret=mid+1,r=mid-1;
        else l=mid+1;
    }
    return ret;
}

void dfs(int u,int pos,int fa)
{
    int qpos,qtop;
    f[u] = Get(que[find(u,pos)],u);
    qpos = Find(u,pos);
    qtop = que[qpos];
    que[qpos] = u;
    for(int i = head[u]; i; i = edge[i].nex)
    {
        if(edge[i].to == fa)continue;
        d[edge[i].to] = d[u] + edge[i].w;
        dfs(edge[i].to,qpos,u);
    }
    que[qpos] = qtop;
}
int main()
{
    scanf("%d",&n);
    int x,y,z;
    for(int i = 1; i < n; i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }
    for(int i = 2; i <= n; i++)scanf("%lld %lld",&w[i],&v[i]);
    dfs(1,0,0);
    printf("%lld",f[2]);
    for(int i = 3; i <= n; i++)printf(" %lld",f[i]);
}

---

最后更新: May 24, 2023