思路 90pts

注意到 $O(n^2)$ 的暴力的能得到 90pts，不妨先考虑一下这个该怎么写。

我们可以考虑 dp，令 dp[i] 为到 i 的时候的最少的答案。

我们可考虑要从 dp[j] 扩展到 dp[i] 只有两种方法，第一种方法也就是在最后一次买东西的时候把羊毛都没买好，后面的直接走到目的地就行了。

第二种方法，就是在走到 j 后走回到买东西的地方，买好东西，然后再走到要搭路的地方搭路。

这样，我们就可以写出一个平方级别的暴力了。

思路 100pts

由于之前是对于所有小于 i 的 j 的两种方法取最小，那么我们可以通过打表发现假设 g(j) 表示第一种方法，f(j) 表示第二种方法，那么 g(j) 是单调递减的，f(j) 是先减后增的，那么我们可以通过二分得到 f 函数的最小值，然后就可以 log 级别得出单个点的答案了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
*/
int m, k, t1, t2;
int a[1000005];
int f(int j, int i) {
    if (j < 0) return -1;
    if (j < 0 || j > i + 1) return 1e18;
    i ++;
    // cout << i << " " << j << " ";
    return a[j] + j * t2 * 2 + max(0ll, k * (i - j) - a[j] + k * j - j * t2) + t1 * (i - j);
}
int findMinByBinarySearch(int low, int high) {
    int th = high - 1;
    while (low <= high) {
        // int mid = low + (high - low) / 2;
        int mid = (low + high + 1) / 2;
        int f_mid = f(mid, th);
        int f_left = f(mid - 1, th);
        int f_right = f(mid + 1, th);

        // std::cout << "检查点: x=" << mid << ", f(x)=" << f_mid 
        // << ", f(x-1)=" << f_left << ", f(x+1)=" << f_right << ", th=" << th << "\n";

        // 如果当前点是谷底（比两边都小）
        if (f_mid <= f_left && f_mid <= f_right) {
            // cout << f_left << " " << f_mid << " " << f_right << "\n";
            // if (f_left == f_mid) return mid - 1;
            // else if (f_right == f_mid) return mid + 1;
            // else return mid;
            return mid;
        }
        // if (f_left == -1) low = mid + 1;
        else if (f_left >= f_mid) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return low;
}
void displayAllPoints(int aa) {
    std::cout << "所有数据点:" << std::endl;
    for (int i = 0; i < aa; ++i) {
        std::cout << "f(" << i << ") = " << f(i, aa - 1) << " , 其中 i = " << aa << ", j = " << i << ", f2(x)=" << a[i] + k * (aa - i) + t1 * (aa - i) << "\n";
    }
    cout << "代码算出来的最小值是：" << f(findMinByBinarySearch(0, aa), aa - 1) << "\n";
    int i = aa;
    int j = i - 1;
    // cout << a[j] + k * (i - j) + t1 * (i - j) << "\n";
    // std::cout << std::endl;
}
const int dev = 0;
void solve() {
    for (int i = 0; i <= m; i ++) a[i] = 0;
    cin >> m >> k >> t1 >> t2;
    for (int i = 1; i <= m; i ++) {
        a[i] = 1e18;
        // a[i] = (i - 1) * t2 * 2 + max(0ll, k - a[i - 1] + k * (i - 1) - (i - 1) * t2) + t1 + a[i - 1];
        int j = i - 1;
        a[i] = min(a[i], a[j] + k * (i - j) + t1 * (i - j));
        a[i] = min(a[i], f(findMinByBinarySearch(0, i), i - 1));
        // for (int j = 0; j < i; j ++) {
        //     a[i] = min(a[i], a[j] + k * (i - j) + t1 * (i - j));
        //     a[i] = min(a[i], a[j] + j * t2 * 2 + max(0ll, k * (i - j) - a[j] + k * j - j * t2) + t1 * (i - j));
        // }
        if (dev == 1) displayAllPoints(i), cout << a[i] << "\n\n";
        if (!dev) cout << a[i] << " ";
        // cout << "\n";
    }
    int i = m;
    cout << "\n";
    if (dev == 2) {
    for (int j = 0; j < i; j ++) {
        cout << a[j] + k * (i - j) + t1 * (i - j) << " " << a[j] + j * t2 * 2 + max(0ll, k * (i - j) - a[j] + k * j - j * t2) + t1 * (i - j) << "\n";
    }
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}