2021CCPC华为云挑战赛 CDN流量调度问题（数论分块，dp）

Desciption

给出 个任务，每个任务需要花费 ，一开始有 个资源，可以最多为它分配 个，总共可以多分配 个，最后总的花费是 。

Solution

补题的时候发现网上没人写题解，还是写一写希望能帮到和我一样的小白。
显然 是经典的数论分块，对于每个 最多有 种取值，这个可以预处理出来。
随后不妨令 表示前 个花费了多少额外资源的最小花费，于是可以 从上一个位置转移过来，总体时间复杂度 。

关于数论分块的一些思考：

Code

/*
 * @Author: Kurisu
 */

#include<bits/stdc++.h>
const int mod = 998244353;
const int N = 1e4 + 5;
#define int long long

int dp[105][10005], a[N], t[N];
std::vector<int> G[105];

int cal(int x, int y) {
    return (x + y - 1) / y;
}

void solve() {
    int n, m; std::cin >> n >> m;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        ans += a[i];
        G[i].clear();
        for (int l = 1, r = 0; l <= a[i]; l = r + 1) {
            int tmp = cal(a[i], l); // make block
            if (tmp == 1) {
                r = a[i];
            } else {
                r = (a[i] - 1) / (tmp - 1);
            }
            G[i].emplace_back(l);
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        std::cin >> t[i];
    }
    for (int i = 1; i <= std::min(m + 1, t[1]); i++) {
        dp[1][i - 1] = cal(a[1], i);
    }
    for (int i = 2; i <= n; i++) { // make dp
        for (int k = 0; k <= t[i] - 1; k++) {
            dp[i][k] = dp[i - 1][k] + a[i];
        }
        for (int j = 0; j < (int)G[i].size(); j++) {
            int x = G[i][j], need = x - 1;
            if (x > t[i]) { // out of range
                break;
            }
            for (int k = 0; k <= m - need; k++) { // k + need <= m
                dp[i][k + need] = std::min(dp[i][k + need], dp[i - 1][k] + cal(a[i], x));
            }
        }
    }
    for (int i = 0; i <= m; i++) {
        ans = std::min(ans, dp[n][i]);
    }
    std::cout << ans << '\n';
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}