题解：P10977 Cut the Sequence

· · 题解

题目传送门

Solution

动态规划题分三步走：设状态，推方程，想优化。

设状态

设状态 f_i 表示前 i 个数每一部分最大整数之和的最小值。

推方程

设 j 为上一个区间的右端点，则要转移的区间转化为 [j+1,i] 且要满足区间和小于 m，于是得到方程：

f_i = \min\left\{f_j + \max_{k=j+1}^{i} a_k\right\}, \quad \text{且} \ 0 \le j \le i-1, \ \sum_{k=j+1}^{i} a_k \le m

想优化

  1. 区间和合法性判断：

    • 对于 \sum_{k=j+1}^{i} a_k \le m 可以用维护前缀和数组 sum_i - sum_j \le m 来判断合法性。
    • 由于 sum_j 的单调不减性，倒序枚举更优。

  2. 区间最大值查询：

    • 使用 ST 表，O(n \log n) 的预处理复杂度加上 O(1) 的查询。

    • 具体实现：

      // 预处理
for (int i = 1; i <= n; i++) st[i][0] = a[i];
int lim = log(n) / log(2) + 1;
for (int j = 1; j < lim; j++)
 for (int i = 1; i <= n - (1 << j) + 1; i++)
     st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (int i = 2; i <= n; i++) logn[i] = logn[i >> 1] + 1;

// 查询
f[i] = min(f[i], f[j] + max(st[j + 1][logn[i - j]], 
        st[i - (1 << logn[i - j]) + 1][logn[i - j]]));

  3. 关键优化：

    • 如果 sum_i \le m，则 f_i = \max(f_{i-1}, a_i)，避免不必要的枚举。

  4. 无解判断：

    • 存在 a_k > m 时直接无解，可在输入时判断。

AC 代码


#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define er puts("")
#define sc putchar(' ')
using namespace std;
const int N = 1e5 + 5;
int sum[N], a[N], f[N], st[N][32], logn[N];

int read() { // 快读
    int x = 0, a = 1; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') a = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return x * a;
}

void write(int x) { // 快写
    if (x < 0) x *= -1, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}

signed main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        if (a[i] > m) { puts("-1"); return 0; } // 判断无解
        sum[i] = sum[i - 1] + a[i]; // 前缀和数组
    }

    // ST表部分
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    int lim = log(n) / log(2) + 1;
    for (int j = 1; j < lim; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    for (int i = 2; i <= n; i++) logn[i] = logn[i >> 1] + 1;

    memset(f, 0x3f, sizeof f); f[0] = 0; // 初始值

    for (int i = 1; i <= n; i++) {
        if (sum[i] <= m) { f[i] = max(f[i - 1], a[i]); continue; } // 关键优化
        for (int j = i - 1; j >= 0; j--) {
            if (sum[i] - sum[j] > m) break; // 后面的一定也不合法
            f[i] = min(f[i], f[j] + max(st[j + 1][logn[i - j]], 
                       st[i - (1 << logn[i - j]) + 1][logn[i - j]]));
        }
    }
    write(f[n]);
    return 0;
}