目录

数位DP

整数划分问题

在这里插入图片描述
每种组合方式都是从大到小排序, 也就是不考虑顺序的组合方式, 例如4 = 1 + 2 + 1和4 = 1 + 1 + 2在本问题中是一种组合方式
因为不考虑顺序, 可以将整数n看作容量是n的背包, 物品的体积是1 ~ n, 每种物品无限次, 求恰好装满背包的方案数, 也就是完全背包问题求方案数
在这里插入图片描述
算法时间复杂度约等于 O ( n 3 ) O(n ^ 3) O(n3), 但是由调和级数得到, 实际复杂度 O ( n 2 log ⁡ n ) O(n ^ 2 \log n) O(n2logn), 考虑完全背包问题的优化方式, 按照状态转移方程进行优化,得到 f[i][j] = f[i - 1][j] + f[i][j - v], 再使用滚动数组进行优化, 因为当前层i状态f[i][j]是由当前层状态得到, 因此不需要从大到小循环体积, 算法时间复杂度降低到 O ( n 2 ) O(n ^ 2) O(n2)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;

int n;
int f[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = i; j <= n; ++j) {
   
            f[j] = (f[j] + f[j - i]) % MOD;
        }
    }

    cout << f[n] << '\n';
    return 0;
}

第二种考虑方式如下
在这里插入图片描述
得到状态转移方程f[i][j] = f[i - 1][j - 1] + f[i - j][j], 算法时间复杂度 O ( n 2 ) O(n ^ 2) O(n2)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;

int n;
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= i; ++j) {
   
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % MOD;
        }
    }

    int res = 0;
    for (int i = 1; i <= n; ++i) res = (res + f[n][i]) % MOD;

    cout << res << '\n';
    return 0;
}

计数问题

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 12;

int l, r;
int f[N];
int cnt_a[10], cnt_b[10];

void init() {
   
    f[0] = 1;
    for (int i = 1; i < N; i++) {
   
        f[i] = f[i - 1] * 10;
    }
}

// 计算从0到n中数字x出现的次数
int count(int n, int x) {
   
    if (n <= 0) return 0;
    
    vector<int> nums;
    while (n) {
   
        nums.push_back(n % 10);
        n /= 10;
    }
    reverse(nums.begin(), nums.end());
    
    int res = 0;
    for (int i = 0; i < nums.size(); i++) {
   
        // 左边部分
        int left = 0;
        for (int j = 0; j < i; j++) {
   
            left = left * 10 + nums[j];
        }
        
        // 右边部分
        int right = 0, right_len = nums.size() - i - 1;
        for (int j = i + 1; j < nums.size(); j++) {
   
            right = right * 10 + nums[j];
        }
        
        // 当前位数字
        int d = nums[i];
        
        // 分类讨论
        if (x) {
   
            // x != 0
            if (d < x) {
   
                res += left * f[right_len];
            } else if (d == x) {
   
                res += left * f[right_len] + right + 1;
            } else {
   
                res += (left + 1) * f[right_len];
            }
        } else {
   
            // x == 0
            if (d == x) {
   
                if (left == 0) {
   
                    res += right + 1;
                } else {
   
                    res += (left - 1) * f[right_len] + right + 1;
                }
            } else if (d > x) {
   
                if (left > 0) {
   
                    res += left * f[right_len];
                }
            }
        }
    }
    
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    while (cin >> l >> r, l || r) {
   
        if (l > r) swap(l, r);
        
        for (int i = 0; i <= 9; i++) {
   
            int cnt_r = count(r, i);
            int cnt_l_minus = count(l - 1, i);
            cout << cnt_r - cnt_l_minus;
            if (i < 9) cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}

度的数量

在这里插入图片描述
相当于将 [ X , Y ] [X, Y] [X,Y]之间的数表示为 B B B进制, 求包含 K K K个 1 1 1的数的个数

数位 d p dp dp基本上问的是某一个区间的满足条件的数字的个数, 可以是使用类似前缀和的思路计算 f ( n ) f(n) f(n), 实际的答案就是 f ( Y ) − f ( X − 1 ) f(Y) - f(X - 1) f(Y)−f(X−1)

使用树的形式考虑
在这里插入图片描述
从最高位开始考虑, 当前分支的左侧是当前位选择 [ 0 , a n − 1 ] [0,a_{n - 1}] [0,an−1​], 右侧是当前位选择 a n a_n an​

假设对于最高位来说填的是 1 1 1, 那么结果就是 C n − 1 k − 1 C_{n - 1} ^ {k - 1} Cn−1k−1​
反之就是 C n − 1 k C_{n - 1} ^ k Cn−1k​

组合数的预处理可以使用递推的方式 C n m = C n − 1 m − 1 + C n − 1 m C_{n} ^ {m} = C_{n - 1} ^ {m - 1} + C_{n - 1} ^ {m} Cnm​=Cn−1m−1​+Cn−1m​

一般的数位 d p dp dp都会使用一个临时变量 l a s t last last记录树的前面的情况, 在本题当中就是已经使用了多少个 1 1 1

#include <bits/stdc++.h>

using namespace std;

const int N = 35;

int f[N][N];
int X, Y, K, B;

void init() {
   
    f[0][0] = 1;
    for (int i = 1; i < N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            if (!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
        }
    }
}

int dp(int n) {
   
    if (!n) return 0;
    vector<int> nums;
    while (n) nums.push_back(n % B), n /= B;

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
   
        int u = nums[i];
        if (u) {
   
            // 当前位填0的情况
            res += f[i][K - last];
            // 当前位 > 1, 当前位可以填1, 但是因为当前位 > 1是非法的
            if (u > 1) {
   
                if (K - last - 1 >= 0) res += f[i][K - last - 1];
                break;
            }
            // 当前位 == 1, 累计last
            else {
   
                last++;
                if (last > K) break;
            }
        }
        if (!i && last == K) res++;
    }

    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    cin >> X >> Y >> K >> B;

    int res = dp(Y) - dp(X - 1);
    cout << res << '\n';
    return 0;
}

数字游戏

在这里插入图片描述
在这里插入图片描述

还是利用前缀和思想, f ( i ) f(i) f(i)表示从 [ 0 , i ] [0, i] [0,i]的不降数的个数, 实际的结果就是 f [ Y ] − f [ X − 1 ] f[Y] - f[X - 1] f[Y]−f[X−1]

在这里插入图片描述
问题是计算, 最高位固定的一共有 n − 1 n - 1 n−1位的不降数的个数
在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 12;

int l, r;
int f[N][N];

void init() {
   
    for (int i = 0; i <= 9; ++i) f[1][i] = 1;
    for (int i = 2; i < N; ++i) {
   
        for (int j = 0; j <= 9; ++j) {
   
            for (int k = j; k <= 9; ++k) {
   
                f[i][j] += f[i - 1][k];
            }
        }
    }
}

int dp(int n) {
   
    if (!n) return 1;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
   
        int u = nums[i];
        for (int j = last; j < u; ++j) res += f[i + 1][j];
        if (u < last) break;
        // 此处相当于处理u == last的情况
        last = u;
        if (!i) res++;
    }

    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    while (cin >> l >> r) cout << dp(r) - dp(l - 1) << '\n';
    return 0;
}

Windy数

在这里插入图片描述
在这里插入图片描述

性质是不含有前导零并且相邻的数字相差至少为2的数字

在这里插入图片描述
最高位不能填 0 0 0

最高位固定, 并且总的位数固定的 W i n d y Windy Windy数的个数, 可以使用 d p dp dp解决, 定义状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示一共 i i i位, 并且最高位是 j j j的 W i n d y Windy Windy数的个数

状态转移看不同点 f [ i ] [ j ] + = f [ i − 1 ] [ k ] , ( ∣ j − k ∣ ≥ 2 ) f[i][j] += f[i - 1][k], (|j - k| \ge 2) f[i][j]+=f[i−1][k],(∣j−k∣≥2)

#include <bits/stdc++.h>

using namespace std;

const int N = 12;

int l, r;
int f[N][N];

void init() {
   
    // 只有一个数字也算windy数
    for (int i = 0; i <= 9; ++i) f[1][i] = 1;
    for (int i = 2; i < N; ++i) {
   
        for (int j = 0; j <= 9; ++j) {
   
            for (int k = 0; k <= 9; ++k) {
   
                if (abs(j - k) >= 2) f[i][j] += f[i - 1][k];
            }
        }
    }
}

int dp(int n) {
   
    if (!n) return 0;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = -2;
    for (int i = nums.size() - 1; i >= 0; --i) {
   
        int u = nums[i];
        for (int j = (i == nums.size() - 1); j < u; ++j) {
   
            if (abs(j - last) >= 2) res += f[i + 1][j];
        }
        if (abs(u - last) >= 2) last = u;
        else break;

        if (!i) res++;
    }

    // 前导零数值00012是不会被累积到答案中的, 但是12应该被累计到答案中, 因此需要累加f[i][j]
    for (int i = 1; i < nums.size(); ++i) {
   
        for (int j = 1; j <= 9; ++j) {
   
            res += f[i][j];
        }
    }

    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << '\n';
    return 0;
}

数字游戏 II

在这里插入图片描述
在这里插入图片描述
左侧分支预处理
定义状态表示 f ( i , j , k ) f(i, j, k) f(i,j,k)表示一共 i i i位并且最高位是 j j j并且所有数字之和 m o d    n = k \mod n = k modn=k的数字的个数
分类还是找不同点, 也就是能从哪个前一个状态转移过来, f [ i ] [ j ] [ k ] + = f [ i − 1 ] [ x ] [ ( n + k − j ) m o d    n ] f[i][j][k] += f[i - 1][x][(n + k - j) \mod n] f[i][j][k]+=f[i−1][x][(n+k−j)modn]

#include <bits/stdc++.h>

using namespace std;

const int N = 12, M = 110;

int l, r, m;
int f[N][N][M];

int get_mod(int val) {
   
    return (val % m + m) % m;
}

void init() {
   
    memset(f, 0, sizeof f);
    for (int i = 0; i <= 9; ++i) f[1][i][i % m]++;
    for (int i = 2; i < N; ++i) {
   
        for (int j = 0; j <= 9; ++j) {
   
            for (int k = 0; k <= 9; ++k) {
   
                for (int r = 0; r <= m; ++r) {
   
                    f[i][j][r] += f[i - 1][k][get_mod(r - j)];
                }
            }
        }
    }
}

int dp(int n) {
   
    if (!n) return 1;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
   
        int u = nums[i];
        for (int j = 0; j < u; ++j) res += f[i + 1][j][get_mod(-last)];
        last += u;
        if (!i && last % m == 0) res++;
    }

    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (cin >> l >> r >> m) {
   
        init();
        cout << dp(r) - dp(l - 1) << '\n';
    }
    return 0;
}

不要62

在这里插入图片描述
在这里插入图片描述

对数字进行拆分, 左侧通过预处理
定义状态表示 f ( i , j ) f(i, j) f(i,j)表示一共有 i i i 位数, 并且最高位是 j j j的符合条件的数字的个数, 条件是当前数字不能为 4 4 4并且当前数字为 6 6 6的情况下次位数字不能为 2 2 2

#include <bits/stdc++.h>

using namespace std;

const int N = 12;

int l, r;
int f[N][N];

void init() {
   
    for (int i = 0; i <= 9; ++i) {
   
        if (i != 4) f[1][i] = 1;
    }

    for (int i = 2; i < N; ++i) {
   
        for (int j = 0; j <= 9; ++j) {
   
            if (j == 4) continue;
            for (int k = 0; k <= 9; ++k) {
   
                if (k == 4) continue;
                if (j == 6 && k == 2) continue;
                f[i][j] += f[i - 1][k];
            }
        }
    }
}

int dp(int n) {
   
    if (!n) return 1;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
   
        int u = nums[i];
        for (int j = 0; j < u; ++j) {
   
            if (j == 4 || (last == 6 && j == 2)) continue;
            res += f[i + 1][j];
        }
        if (u == 4) break;
        if (last == 6 && u == 2) break;
        last = u;

        if (!i) res++;
    }

    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    while (cin >> l >> r, l || r) {
   
        cout << dp(r) - dp(l - 1) << '\n';
    }

    return 0;
}

恨7不成妻(HDU4507)

在这里插入图片描述
带有多个条件的数位 d p dp dp, 分析方法还是将数字拆分, 从高位向低位考虑
在这里插入图片描述
定义状态表示 f [ i ] [ j ] [ a ] [ b ] f[i][j][a][b] f[i][j][a][b]代表一共 i i i位, 并且最高位是 j j j, 并且当前数字 m o d    n = a \mod n = a modn=a, 并且所有位的和的余数等于 b b b的所有数的平方和

可以知道上一个状态是 f [ i − 1 ] [ k ] [ a − j × 1 0 i − 1 ] [ b − j ] f[i - 1][k][a - j \times 10 ^ {i - 1}][b - j] f[i−1][k][a−j×10i−1][b−j]

将平方和展开
j … ⏞ f ( i , j , a 1 b )  位  ( j A 1 ) 2 + ( j A 2 ) 2 + ⋯ + ( j A t ) 2 j 2 × 1 0 i − 1 × t + 2 × j × 1 0 i − 1 × ( A 1 + A 2 + ⋯ + A t ) + A 1 2 + A 2 2 + ⋯ + A t 2 \begin{array}{l} \overbrace{j \ldots}^{f\left(i, j, a_{1} b\right)} \text { 位 } \\ \left(j A_{1}\right)^{2}+\left(j A_{2}\right)^{2}+\cdots+\left(j A_{t}\right)^{2} \\ \frac{j^{2} \times 10^{i-1} \times t+2 \times j \times 10^{i-1} \times \left(A_{1}+A_{2}+\cdots+A_{t}\right)+{}}{} \\ \frac{A_{1}^{2}+A_{2}^{2}+\cdots+A t^{2}}{} \end{array} j… ​f(i,j,a1​b)​ 位 (jA1​)2+(jA2​)2+⋯+(jAt​)2j2×10i−1×t+2×j×10i−1×(A1​+A2​+⋯+At​)+​A12​+A22​+⋯+At2​​

为了计算平方和, 需要存储三个状态, 数字的个数 t t t, 每个数字的和 s s s, 每个数字的平方和 s 2 s_2 s2​
j A 1 + j A 2 + … + j A t = j × 1 0 j − 1 × t + ( A 1 + A 2 + … + A t ) j A_{1}+j A_{2}+\ldots+j A_{t}=j \times 10^{j-1} \times t+\left(A_{1}+A_{2}+\ldots+A_{t}\right) jA1​+jA2​+…+jAt​=j×10j−1×t+(A1​+A2​+…+At​)

如何根据last_a计算当前的 a a a
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 20, MOD = 1e9 + 7;

int l, r;
struct F {
   
    int s0, s1, s2;
} f[N][10][7][7];
int pow7[N], pow9[N];

int get_mod(LL val, int mod) {
   
    return (val % mod + mod) % mod;
}

void init() {
   
    for (int i = 0; i <= 9; ++i) {
   
        if (i == 7) continue;
        auto &v = f[1][i][i % 7][i % 7];
        v.s0++;
        v.s1 += i;
        v.s2 += i * i;
    }

    LL pow = 10;
    for (int i = 2; i < N; ++i, pow *= 10) {
   
        for (int j = 0; j <= 9; ++j) {
   
            if (j == 7) continue;
            for (int a = 0; a < 7; ++a) {
   
                for (int b = 0; b < 7; ++b) {
   
                    for (int k = 0; k <= 9; ++k) {
   
                        if (k == 7) continue;
                        auto &val1 = f[i][j][a][b];
                        auto &val2 = f[i - 1][k][get_mod(a - j * pow, 7)][get_mod(b - j, 7)];
                        // 平方和公式展开计算状态转移
                        val1.s0 = (val1.s0 + val2.s0) % MOD;
                        val1.s1 = (val1.s1 + val2.s1 + j * (pow % MOD) % MOD * val2.s0) % MOD;
                        val1.s2 = (val1.s2 +
                                   (LL)j * j % MOD * (pow % MOD) % MOD * (pow % MOD) % MOD * val2.s0 % MOD +
                                   val2.s2 +
                                   2LL * j % MOD * (pow % MOD) % MOD * val2.s1 % MOD) % MOD;
                    }
                }
            }
        }
    }

    // 预处理10 ^ n对7和1e9 + 7取模的结果
    pow7[0] = pow9[0] = 1;
    for (int i = 1; i < N; ++i) {
   
        pow7[i] = pow7[i - 1] * 10 % 7;
        pow9[i] = (LL) pow9[i - 1] * 10 % MOD;
    }
}

// 计算整个数字的余数不等于a并且各位数字之和的余数不等于b的情况
F get(int i, int j, int a, int b) {
   
    int s0 = 0, s1 = 0, s2 = 0;
    for (int x = 0; x < 7; ++x) {
   
        for (int y = 0; y < 7; ++y) {
   
            if (x != a && y != b) {
   
                auto &val = f[i][j][x][y];
                s0 = (s0 + val.s0) % MOD;
                s1 = (s1 + val.s1) % MOD;
                s2 = (s2 + val.s2) % MOD;
            }
        }
    }

    return {
   s0, s1, s2};
}

int dp(LL n) {
   
    if (!n) return 0;
    LL val = n % MOD;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    // last_a存储的是从最高位开始到当前位置前一个位置的组成的数字, last_b存储的是从最高位开始到当前位前一个位置的每一位的数字之和
    LL last_a = 0, last_b = 0;
    LL res = 0;
    for (int i = nums.size() - 1; i >= 0; --i) {
   
        int u = nums[i];
        for (int j = 0; j < u; ++j) {
   
            if (j == 7) continue;
            int a = get_mod(-last_a * pow7[i + 1], 7);
            int b = get_mod(-last_b, 7);
            auto v = get(i + 1, j, a, b);
            res = (res +
                    (LL) (last_a % MOD) * (last_a % MOD) % MOD * pow9[i + 1] % MOD * pow9[i + 1] % MOD * v.s0 % MOD +
                   v.s2 +
                    (LL) 2 * last_a % MOD * pow9[i + 1] % MOD * v.s1 % MOD) % MOD;
        }

        if (u == 7) break;
        last_a = last_a * 10 + u;
        last_b += u;

        // 处理完了所有数字
        if (!i && last_a % 7 && last_b % 7) res = (res + val * val % MOD) % MOD;
    }

    return res % MOD;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    int T;
    cin >> T;
    while (T--) {
   
        LL l, r;
        cin >> l >> r;
        cout << get_mod(dp(r) - dp(l - 1), MOD) << '\n';
    }

    return 0;
}

单调队列优化DP

最大子序和

在这里插入图片描述
定义状态表示 f [ i ] f[i] f[i]表示以 a i a_i ai​为结尾的长度不超过 m m m的连续子序列, 属性是最大连续子序列和, 朴素做法时间复杂度 O ( n 2 ) O(n ^ 2) O(n2)
在有限的集合当中求最值或者最优解
在这里插入图片描述
将集合进行分类, 将所有子序列按照结尾的数值进行分类 a k a_k ak​, 只需要求每一类的最大值, 然后对这些类取 m a x max max
在这里插入图片描述
通过前缀和预处理 s [ k ] s[k] s[k]代表 s 0 + s 1 + . . . + s k s_0 + s_1 + ... + s_k s0​+s1​+...+sk​, 假设枚举的前面的连续子序列和的长度是 j j j, r e s = max ⁡ ( r e s , s [ k ] − s [ k − j ] ) res = \max(res, s[k] - s[k - j]) res=max(res,s[k]−s[k−j]), 也就是找到最小的 s [ k − j ] s[k - j] s[k−j], 也就是在长度不超过 m m m的区间中找最小值, 区间求最值可以使用单调队列优化
优化后算法时间复杂度 O ( n ) O(n) O(n)

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
const unsigned int INF = 1 << 31;

int n, m;
int w[N], q[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= n; ++i) w[i] += w[i - 1];

    int h = 0, t = -1;
    q[++t] = 0;

    int res = -INF;
    for (int i = 1; i <= n; ++i) {
   
        while (h <= t && i - q[h] > m) h++;
        res = max(res, w[i] - w[q[h]]);
        while (h <= t && w[i] <= w[q[t]]) t--;
        q[++t] = i;
    }

    cout << res << '\n';
    return 0;
}

因为 q [ h ] q[h] q[h]可能是刚刚加入的 i i i, 因此不能放在入队语句之后计算最大值
实际上是在 [ m a x ( 0 , i − m ) , i − 1 ] [max(0, i-m), i-1] [max(0,i−m),i−1]该区间寻找最小值, [ 0 , 0 ] [0, 0] [0,0]子段的和应该是 0 0 0, 因此只能初始化为 0 0 0, 并且需要初始化将 0 0 0入队

修剪草坪

在这里插入图片描述
定义状态表示 f ( i ) f(i) f(i)表示考虑前 i i i只奶牛, 属性是最大值, 状态转移观察第一个不同的位置, 不选 i i i的最大值 f ( i − 1 ) f(i - 1) f(i−1)
在这里插入图片描述
按照前面连续奶牛的数量进行集合的划分
在这里插入图片描述
计算效率的最大值, a n s = f ( i − j − 1 ) + s i − s i − j ans = f(i - j - 1) + s_i - s_{i - j} ans=f(i−j−1)+si​−si−j​, s s s是前缀和, a n s = { f ( i − j − 1 ) − s i − j } + s i ( 0 ≤ j ≤ k ) ans = \{f(i - j - 1) - s_{i - j}\} + s_i (0 \le j \le k) ans={ f(i−j−1)−si−j​}+si​(0≤j≤k), 前面的是变量, 后面的是定值, 前面的求最大值就是在 i i i前面不超过 k k k的长度的窗口求最大值, 使用单调队列优化, 算法时间复杂度 O ( n ) O(n) O(n)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, k;
LL w[N], f[N];

LL get(int i) {
   
    return f[i - 1] - w[i];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
   
        cin >> w[i];
        w[i] += w[i - 1];
    }

    int q[N], h = 0, t = -1;
    q[++t] = 0;
    
    for (int i = 1; i <= n; ++i) {
   
        while (h <= t && i - q[h] > k) h++;
        f[i] = max(f[i - 1], get(q[h]) + w[i]);
        while (h <= t && get(q[t]) < get(i)) t--;
        q[++t] = i;
    }

    cout << f[n] << '\n';

    return 0;
}

烽火传递

在这里插入图片描述
定义状态表示 f ( i ) f(i) f(i)表示考虑前 i i i个烽火台, 并且点燃第 i i i个烽火台的所有方案的集合, 属性是最小值
在这里插入图片描述
假设当前点燃了第 i i i个烽火台, 那么距离 i i i最远的点燃烽火台的位置就是 i − m + 1 i - m + 1 i−m+1, 如果再远就是非法的, f ( i ) = w i + min ⁡ { f ( k ) } f(i) = w_i + \min\{ f(k)\} f(i)=wi​+min{ f(k)}, 区间求极值问题, 使用单调队列优化, 算法时间复杂度 O ( n ) O(n) O(n)

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int w[N], f[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    memset(f, 0x3f, sizeof f);

    f[0] = 0;
    int q[N], h = 0, t = -1;
    q[++t] = 0;
    for (int i = 1; i <= n; ++i) {
   
        while (h <= t && i - q[h] > m) h++;
        f[i] = min(f[i], w[i] + f[q[h]]);
        while (h <= t && f[i] <= f[q[t]]) t--;
        q[++t] = i;
    }

    int res = INF;
    for (int i = n - m + 1; i <= n; ++i) res = min(res, f[i]);

    cout << res << '\n';
    return 0;
}

绿色通道(二分 + 单调队列优化 d p dp dp)

在这里插入图片描述
在这里插入图片描述
因为最长空题段越长, 老师生气程度越高, 具有单调性, 假设当前最长最长空题段是 k k k, 定义函数check(int k), 判断在最长空题段不超过 k k k的情况下最短抄题的时间是否超过了 t t t, 如果超过了 t t t, 需要增大最长空题段的长度, 否则可以减少最长空题段的长度, 算法时间复杂度 O ( n log ⁡ a i ) O(n \log a_i) O(nlogai​)

注意边界条件, 因为要求的最长空题段不超过 k k k, 也就是说前一个写题目的点最远是 i − k i - k i−k而不是 i − k + 1 i - k + 1 i−k+1, 因此实际上滑动窗口大小是 k + 1 k + 1 k+1

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10, INF = 0x3f3f3f3f;

int n, T;
int w[N], f[N];

bool check(int k) {
   
    int q[N], h = 0, t = -1;
    q[++t] = 0;
    for (int i = 1; i <= n; ++i) {
   
        while (h <= t && i - q[h] > k + 1) h++;
        f[i] = w[i] + f[q[h]];
        while (h <= t && f[i] < f[q[t]]) t--;
        q[++t] = i;
    }

    int res = INF;
    for (int i = n - k; i <= n; ++i) res = min(res, f[i]);
    return res <= T;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> T;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    int l = 0, r = n;
    while (l < r) {
   
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << '\n';
    return 0;
}

旅行问题(区间 d p dp dp + 单调队列优化 d p dp dp)

在这里插入图片描述
在这里插入图片描述
因为顺时针和逆时针是对称的, 首先先考虑顺时针, 将环形的问题展开为链状, 如上图
在这里插入图片描述
将每个地方的值设为 t = o i − d i t = o_i - d_i t=oi​−di​, 如果 t < 0 t < 0 t<0说明无法从 i i i位置移动到 i + 1 i + 1 i+1位置
因为每个地点都能加油, 因此假设前面还剩油是 s s s, s + o i − d i ≥ 0 s + o_i - d_i \ge 0 s+oi​−di​≥0, 就是能到达下一个位置的, 因此从当前位置能顺时针走完一圈等价于 min ⁡ { s u m i } ≥ 0 \min \{ sum_i\} \ge 0 min{ sumi​}≥0, s u m i sum_i sumi​是 t t t的前缀和

在这里插入图片描述
因为计算的每个点为起点后面的最小值, 因此需要从后向前枚举, 假设最小值位置是 j j j, 只需要检查 s j − s i − 1 ≥ 0 s_j - s_{i - 1} \ge 0 sj​−si−1​≥0, 算法时间复杂度 O ( n ) O(n) O(n)
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e6 + 10;

int n, o[N], d[N];
LL s[N];
bool st[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        cin >> o[i] >> d[i];
        s[i] = s[i + n] = o[i] - d[i];
    }

    for (int i = 1; i <= 2 * n; ++i) s[i] += s[i - 1];

    int q[N], h = 0, t = -1;
    for (int i = 2 * n; i >= 1; --i) {
   
        while (h <= t && i - q[h] + 1 > n) h++;
        while (h <= t && s[i] < s[q[t]]) t--;
        q[++t] = i;
        if (i <= n && s[q[h]] - s[i - 1] >= 0) st[i] = true;
    }

    d[0] = d[n];
    for (int i = 1; i <= n; ++i) s[i] = s[i + n] = o[i] - d[i - 1];
    for (int i = 2 * n; i >= 0; --i) s[i] += s[i + 1];

    h = 0, t = -1;
    for (int i = 1; i <= 2 * n; ++i) {
   
        while (h <= t && q[h] - i + 1 > n) h++;
        while (h <= t && s[i] < s[q[t]]) t--;
        q[++t] = i;
        if (i >= n + 1 && s[q[h]] - s[i + 1] >= 0) st[i - n] |= true;
    }

    for (int i = 1; i <= n; ++i) {
   
        cout << (st[i] ? "TAK" : "NIE") << '\n';
    }
    return 0;
}

在这里插入图片描述

因为要求长度为 n n n的区间的最小值, 而当前位置 s i s_i si​是有可能作为最小值出现的, 因此必须在 i i i入队之后进行判断

理想的正方形(并无 d p dp dp做法)

在这里插入图片描述
n × n n \times n n×n的正方形内所有数最大值减最小值的差最小, 暴力做法就是从起始位置开始枚举所有正方形
实际还是将答案集合进行分类, 将目标正方形按行和列进行分类, 分步去处理(借助 d p dp dp的思想)
先求每行长度为 n n n的最值, 也就是滑动窗口最大值(最小值), 再求每一列长度为 n n n的最大值(最小值)
在这里插入图片描述
具体来说, 将每一行最大值压缩到右侧(因为计算最大值和最小值是从左向右遍历的), 然后在此基础上求列的最大值, 那么整个矩形的最大值得到了, 同理得到矩形的最小值
因为行和列的长度都是 N N N, 算法时间复杂度 O ( N 2 ) O(N ^ 2) O(N2)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int a, b, n;
int w[N][N];
int minv[N][N], maxv[N][N];
int r_max[N], r_min[N], c_max[N], c_min[N];

void get_max(int a[], int res[], int len) {
   
    int q[N], h = 0, t = -1;
    for (int i = 1; i <= len; ++i) {
   
        while (h <= t && i - q[h] + 1 > n) h++;
        while (h <= t && a[i] > a[q[t]]) t--;
        q[++t] = i;
        res[i] = a[q[h]];
    }
}

void get_min(int a[], int res[], int len) {
   
    int q[N], h = 0, t = -1;
    for (int i = 1; i <= len; ++i) {
   
        while (h <= t && i - q[h] + 1 > n) h++;
        while (h <= t && a[i] < a[q[t]]) t--;
        q[++t] = i;
        res[i] = a[q[h]];
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> a >> b >> n;

    for (int i = 1; i <= a; ++i) {
   
        for (int j = 1; j <= b; ++j) {
   
            cin >> w[i][j];
        }
    }

    // 计算行最大值
    for (int i = 1; i <= a; ++i) {
   
        get_max(w[i], maxv[i], b);
        get_min(w[i], minv[i], b);
    }

    int res = INF;
    
    // 外层遍历每一列, 内层将每一行的极值存储到临时数组当中也就是r_max, r_min
    for (int j = n; j <= b; ++j) {
   
        for (int i = 1; i <= a; ++i) {
   
            r_max[i] = maxv[i][j];
            r_min[i] = minv[i][j];
        }
        get_max(r_max, c_max, a);
        get_min(r_min, c_min, a);
        for (int i = n; i <= a; ++i) res = min(res, c_max[i] - c_min[i]);
    }

    cout << res << '\n';

    return 0;
}

斜率优化DP

任务安排1

在这里插入图片描述
n n n个机器成一个序列来执行, 将任务分为若干批, 在执行每一批任务之前, 需要话 S S S时间启动机器

每一批开始有一个启动时间 S S S, 会对后面所有任务的结束时刻会增加 S S S
将增加的启动时间对未来的影响, 计算到当前区间中,
因为结束时刻的时间都推迟了 S S S, 那么产生的花费就是 S × ( C j + 1 + C j + 2 + C j + 3 + . . . + C n ) S \times (C_{j + 1} + C_{j + 2} + C_{j + 3} + ... + C_n) S×(Cj+1​+Cj+2​+Cj+3​+...+Cn​)

状态表示 f ( i ) f(i) f(i), 处理完前 i i i个任务的所有方案, 属性是最小值
状态转移找不同点, 观察最后一批任务是如何划分的 , 也可以看前一批任务的最后一个任务的位置, 设为 j j j
在这里插入图片描述
状态转移方程 f i = min ⁡ ( f [ j ] + S u m T i × ( S u m C i − S u m C j ) + S × ( S u m C n − S u m C j ) ) f_i = \min ({f[j] + SumT_i \times (SumC_i - SumC_j) + S \times (SumC_n - SumC_j)}) fi​=min(f[j]+SumTi​×(SumCi​−SumCj​)+S×(SumCn​−SumCj​))

算法时间复杂度 O ( n 2 ) O(n ^ 2) O(n2)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5010;

int n, s;
LL t[N], c[N];
LL f[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
   
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }

    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j < i; ++j) {
   
            LL val = f[j] + (LL) t[i] * (c[i] - c[j]) + (LL) s * (c[n] - c[j]);
            f[i] = min(f[i], val);
        }
    }

    cout << f[n] << '\n';

    return 0;
}

任务安排2

在这里插入图片描述

注意到 N N N的数据范围变为 3 × 1 0 5 3 \times 10 ^ 5 3×105, 不能使用朴素的 O ( n 2 ) O(n ^ 2) O(n2)做法, 需要进行优化

对状态转移方程进行整理
f i = min ⁡ ( f [ j ] + S u m T i × ( S u m C i − S u m C j ) + S × ( S u m C n − S u m C j ) ) f_i = \min ({f[j] + SumT_i \times (SumC_i - SumC_j) + S \times (SumC_n - SumC_j)}) fi​=min(f[j]+SumTi​×(SumCi​−SumCj​)+S×(SumCn​−SumCj​))

提出常量
f i = S u m T i × S u m C i + S × S u m C n + min ⁡ ( f j − S u m T i × S u m C j − S × S u m C j ) f_i = SumT_i \times SumC_i + S \times SumC_n + \min (f_j - SumT_i \times SumC_j - S \times SumC_j) fi​=SumTi​×SumCi​+S×SumCn​+min(fj​−SumTi​×SumCj​−S×SumCj​)

因为计算的是当前 i i i的最小值, 可以将 i i i的变量看作常数, 设 t = S u m T i × S u m C i + S × S u m C n t = SumT_i \times SumC_i + S \times SumC_n t=SumTi​×SumCi​+S×SumCn​

f i = min ⁡ ( f j − ( S u m T i + S ) × S u m C j + t ) f_i = \min (f_j - (SumT_i + S) \times SumC_j + t) fi​=min(fj​−(SumTi​+S)×SumCj​+t)

将 f j f_j fj​看作是 y y y, 将 S u m C j SumC_j SumCj​看作是 x x x, 可以看作是直线方程, 设 t ′ = t + f i t' = t +f_i t′=t+fi​

f j = ( S u m T i + S ) × S u m C j + t ′ f_j = (SumT_i + S) \times SumC_j + t' fj​=(SumTi​+S)×SumCj​+t′

看作 y = k x + b y = kx + b y=kx+b, 斜率是 k = S u m T i + S k = SumT_i + S k=SumTi​+S是正整数,并且取不到 + ∞ +\infty +∞

j j j的范围是 0 ≤ j ≤ i − 1 0 \le j \le i - 1 0≤j≤i−1, 目标是 f i f_i fi​最小, t ′ = S u m T i × S u m C i + S × S u m C n + f i t' = SumT_i \times SumC_i + S \times SumC_n + f_i t′=SumTi​×SumCi​+S×SumCn​+fi​,求 f i f_i fi​最小值, 也就是求 t ′ t' t′的最小值, 当 i i i固定, k k k也是固定的

对于每个坐标对 ( S u m C j , f j ) (SumC_j, f_j) (SumCj​,fj​), 带入直线方程, 能计算出常量 t ′ t' t′, 也就能求得 f i f_i fi​

在这里插入图片描述
将所有的点加入到坐标系中, 因为斜率是固定的, 并且 b b b是正数, 第一次相切的点就是最小的截距 b b b, 也就是最小的 f i f_i fi​

在这里插入图片描述

不是所有的点都会作为答案累计, 任选两个点, 如果有点在该直线的上方, 那么在上方的点一定不会作为答案累计, 最终得到的就是凸包的下边界, 计算可能用到的点只需要维护凸包的下边界

在这里插入图片描述
假设直线的斜率是 k k k, 取得最小值的位置是第一个大于 k k k的斜率的第一个点, 上图的例子就是 k 2 k_2 k2​斜率的第一个点, 取得最小值

凸包点的斜率是单调的, 相当于在单调序列中, 找第一个大于 k k k的斜率的直线的第一个点

  • S u m T i SumT_i SumTi​是单调递增的, 枚举每条直线的斜率也是单调递增的
  • S u m C i SumC_i SumCi​也是单调递增的, 在凸包中加点的时候, 点的横坐标也是单调递增的

在这里插入图片描述

如果满足上述两个条件, 寻找斜率 k i k_i ki​的情况就不需要二分算法, 在查询的时候, 可以将队列的头将小于当前 k k k的直线斜率都删掉
插入的时候, 因为横坐标是单调增的, 将所有不满足要求的点删掉, 也就是说将队尾不在凸包上的点全部删掉

因为每个点只会进队出队一次, 算法时间复杂度 O ( n ) O(n) O(n)

在这里插入图片描述

队列出队入队情况

  • f 2 − f 1 S u m C 2 − S u m C 1 ≤ S u m T i + S \frac{f_2 - f_1}{SumC_2 - SumC_1} \le SumT_i + S SumC2​−SumC1​f2​−f1​​≤SumTi​+S
  • f t − f t − 1 S u m C t − S u m C t − 1 ≥ f i − f t − 1 S u m C i − S u m C t − 1 \frac{f_t - f_{t - 1}}{SumC_t - SumC_{t - 1}} \ge \frac{f_i - f_{t - 1}}{SumC_i - SumC_{t - 1}} SumCt​−SumCt−1​ft​−ft−1​​≥SumCi​−SumCt−1​fi​−ft−1​​

注意因为至少两个点才能构成一条直线, 因此队列中至少有两个点才能进行更新单调队列的操作

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 3e5 + 10;

int n, s;
LL c[N], st[N];
int q[N];
LL f[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
   
        cin >> st[i] >> c[i];
        st[i] += st[i - 1];
        c[i] += c[i - 1];
    }

    int h = 0, t = -1;
    q[++t] = 0;

    for (int i = 1; i <= n; ++i) {
   
        LL k = st[i] + s;
        while (h < t && f[q[h + 1]] - f[q[h]] <= k * (c[q[h + 1]] - c[q[h]])) h++;

        int j = q[h];
        f[i] = f[j] + st[i] * (c[i] - c[j]) + s * (c[n] - c[j]);

        while (h < t && (f[q[t]] - f[q[t - 1]]) * (c[i] - c[q[t - 1]]) >= (f[i] - f[q[t - 1]]) * (c[q[t]] - c[q[t - 1]])) t--;
        q[++t] = i;
    }

    cout << f[n] << '\n';

    return 0;
}

任务安排3

在这里插入图片描述
注意到 T i T_i Ti​可以是负数

  • 斜率 k = S u m C i + S k = SumC_i + S k=SumCi​+S, 不再具有单调性
  • 新加的点 S u m C j SumC_j SumCj​一定是单调递增的, 横坐标单调
  1. 查询的时候只能二分查找第一个大于 k k k的位置
  2. 插入的时候, 可以将队尾不在凸包上的点删除

算法时间复杂度变为 O ( n log ⁡ n ) O(n \log n) O(nlogn)

注意在比较斜率的时候, f [ q [ t ] ] − f [ q [ t − 1 ] ] f[q[t]] - f[q[t - 1]] f[q[t]]−f[q[t−1]]量级是 1 0 9 10 ^ 9 109, 并且 c [ i ] − c [ q [ t − 1 ] ] c[i] - c[q[t - 1]] c[i]−c[q[t−1]]的量级也是 1 0 9 10 ^ 9 109, 乘积会超过 1 0 18 10 ^ {18} 1018, 需要转化为 d o u b l e double double进行比较

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 3e5 + 10;

int n, s;
LL c[N], st[N];
int q[N];
LL f[N];

int find(int k, int h, int t) {
   
    int l = h, r = t;
    while (l < r) {
   
        int mid = l + r >> 1;
        if (f[q[mid + 1]] - f[q[mid]] > k * (c[q[mid + 1]] - c[q[mid]])) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
   
        cin >> st[i] >> c[i];
        c[i] += c[i - 1];
        st[i] += st[i - 1];
    }

    int h = 0, t = -1;
    q[++t] = 0;
    for (int i = 1; i <= n; ++i) {
   
        int j = q[find(st[i] + s, h, t)];
        f[i] = f[j] + st[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
        while (h < t && (double) (f[q[t]] - f[q[t - 1]]) * (c[i] - c[q[t - 1]]) >= (double) (f[i] - f[q[t - 1]]) * (c[q[t]] - c[q[t - 1]])) t--;
        q[++t] = i;
    }

    cout << f[n] << '\n';
    return 0;
}

运输小猫

在这里插入图片描述
在这里插入图片描述
N N N座山, M M M只猫, P P P位饲养员, 每两座山之间的距离已知是 d i d_i di​
在这里插入图片描述
派 p p p个饲养员, 将已经玩完毕的猫带走, 要求计算所有猫等待时间的最小值是多少

  • 预处理 d i d_i di​的前缀和, 表示从 1 1 1到 i i i的距离
  • 对于每个小猫有两个属性, 玩耍的结束时刻 t i t_i ti​, 以及当前山距离第一座山的距离 d i d_i di​
  • 假设饲养员的出发时间点是 S S S, 能接到当前小猫等价于 S + d i ≥ t i S + d_i \ge t_i S+di​≥ti​, 也就是 S ≥ t i − d i S \ge t_i - d_i S≥ti​−di​
  • 如果想接到当前小猫, 饲养员出发的最早时间是 t i − d i t_i - d_i ti​−di​
  • 如果饲养员晚出发了 Δ t \Delta t Δt, 那么 S + d i + Δ t S + d_i + \Delta t S+di​+Δt就是到达时间, 小猫等待的时间等于 S + d i + Δ t − t i S + d_i + \Delta t - t_i S+di​+Δt−ti​, 也就是 S i + Δ t − ( t i − d i ) S_i + \Delta t - (t_i - d_i) Si​+Δt−(ti​−di​)
  • 令 A i = t i − d i A_i = t_i - d_i Ai​=ti​−di​, 也就是对于每只小猫, 饲养员出发的最早时刻
  • 对所有小猫按照饲养员除出发的最早时刻从小到大排序, 饲养员每次出发相当于接走连续的一批小猫

在这里插入图片描述
假设接走蓝***域内的小猫, 因为 A i A_i Ai​已经排过序, 因此总的等待时间等于 A 3 − A 1 + A 3 − A 2 + A 3 − A 3 = A 3 × 3 − ( S u m 3 − S u m 0 ) A_3 - A_1 + A_3 - A_2 + A_3 - A_3 = A_3 \times 3 - (Sum_3 - Sum_0) A3​−A1​+A3​−A2​+A3​−A3​=A3​×3−(Sum3​−Sum0​)

问题就变成了, 如何分批接走小猫(最多分出 p p p组), 使得小猫等待的总时间最少

  • 定义状态表示 f ( j , i ) f(j, i) f(j,i)表示考虑前 i i i只小猫并且已经分了 j j j组的集合, 属性是小猫等待时间的最小值
  • 状态转移看每个方案的不同点, 和任务安排问题类似, 按照最后一批小猫是如何划分的进行分类
  • 假设前一批最后一个小猫是 k k k, A i A_i Ai​的前缀和是 S i S_i Si​, 有状态转移方程

f ( j , i ) = min ⁡ { f ( j − 1 , k ) + A i × ( i − k ) − ( S i − S k ) } f(j, i) = \min \{f(j - 1, k) + A_i \times (i - k) - (S_i - S_k) \} f(j,i)=min{ f(j−1,k)+Ai​×(i−k)−(Si​−Sk​)}

可以将 i i i相关的看作常量, 变量只有 k k k, 0 ≤ k ≤ i − 1 0 \le k \le i - 1 0≤k≤i−1
整理方程得到

f ( j , i ) = f ( j − 1 , k ) + A i × i − A i × k − S i + S k f(j, i) = f(j - 1, k) + A_i \times i - A_i \times k - S_i + S_k f(j,i)=f(j−1,k)+Ai​×i−Ai​×k−Si​+Sk​

整理得到

f ( j − 1 , k ) + S k = A i × k + S i − A i × i + f ( j , i ) f(j - 1, k) + S_k = A_i \times k + S_i - A_i \times i + f(j, i) f(j−1,k)+Sk​=Ai​×k+Si​−Ai​×i+f(j,i)

将 f ( j − 1 , k ) + S k f(j - 1, k) + S_k f(j−1,k)+Sk​视作 y y y, 将 A i A_i Ai​视作斜率 k k k, k k k视作 x x x, S i − A i × i + f ( j , i ) S_i - A_i \times i + f(j, i) Si​−Ai​×i+f(j,i)视为斜率 b b b, 得到直线 y = k x + b y = kx + b y=kx+b

因为斜率 k = A i k = A_i k=Ai​单调递增, 并且变量 x x x也是单调递增的 ( 0 ≤ k ≤ i − 1 ) (0 \le k \le i - 1) (0≤k≤i−1), 可以使用单调队列维护下凸壳
算法时间复杂度 O ( N P ) O(NP) O(NP), 最坏情况下 1 0 7 10 ^ 7 107复杂度, 可以通过

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 1e5 + 10, P = 110;

int n, m, p;
LL d[N], st[M], A[M], s[M];
LL f[P][M];
int q[M];

inline LL get_y(int j, int k) {
   
    return f[j - 1][k] + s[k];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> p;
    for (int i = 2; i <= n; ++i) {
   
        cin >> d[i];
        d[i] += d[i - 1];
    }

    for (int i = 1; i <= m; ++i) {
   
        LL h;
        cin >> h >> st[i];
        A[i] = st[i] - d[h];
    }

    sort(A + 1, A + m + 1);
    for (int i = 1; i <= m; ++i) s[i] = s[i - 1] + A[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= p; ++i) f[i][0] = 0;

    for (int j = 1; j <= p; ++j) {
   
        int h = 0, t = -1;
        q[++t] = 0;
        for (int i = 1; i <= m; ++i) {
   
            while (h < t && get_y(j, q[h + 1]) - get_y(j, q[h]) <= A[i] * (q[h + 1] - q[h])) h++;
            int k = q[h];
            f[j][i] = f[j - 1][k] + A[i] * (i - k) - (s[i] - s[k]);
            while (h < t && (get_y(j, q[t]) - get_y(j, q[t - 1])) * (i - q[t - 1]) >=
            (get_y(j, i) - get_y(j, q[t - 1])) * (q[t] - q[t - 1])) t--;
            q[++t] = i;
        }
    }

    cout << f[p][m] << '\n';
    return 0;
}