专栏文章

题解：P10977 Cut the Sequence

HHZEason_Ai
P10977题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipkamns
此快照首次捕获于
2025/12/03 13:23
3 个月前
此快照最后确认于
2025/12/03 13:23
3 个月前
查看原文
题目传送门

Solution

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

设状态

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

推方程

设 jj 为上一个区间的右端点，则要转移的区间转化为 [j+1,i][j+1,i] 且要满足区间和小于 mm，于是得到方程：
fi=min⁡{fj+max⁡k=j+1iak},且 0≤j≤i−1, ∑k=j+1iak≤mf_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. 区间和合法性判断：
    • 对于 ∑k=j+1iak≤m\sum_{k=j+1}^{i} a_k \le m 可以用维护前缀和数组 sumi−sumj≤msum_i - sum_j \le m 来判断合法性。
    • 由于 sumjsum_j 的单调不减性，倒序枚举更优。
  2. 区间最大值查询：
    • 使用 ST 表，O(nlog⁡n)O(n \log n) 的预处理复杂度加上 O(1)O(1) 的查询。
    • 具体实现： CPP
      // 预处理
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. 关键优化：
    • 如果 sumi≤msum_i \le m，则 fi=max⁡(fi−1,ai)f_i = \max(f_{i-1}, a_i)，避免不必要的枚举。
  4. 无解判断：
    • 存在 ak>ma_k > m 时直接无解，可在输入时判断。

AC 代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...