P14597 递增 / Rastući

给我翻过来!

—标曹丕

题目大意

给定一个长度为

n

的正整数序列，要求将其划分为若干段，使得每一段的和严格不降，求最少划分段数，并输出一种划分方案（按每段和从小到大输出）。

解题思路

初步分析

~~暴力显然超时~~初步分析可知后切割的段对先切割的段的答案没有影响，不难想到 DP 实现。
其次涉及到区间和查询，所以使用前缀和进行优化。

状态定义

设

dp_{i,j}

表示前

i

个元素划分为

j

段时，最后一段和的最小值。
为什么这么设计呢，显然转移时只需要关注上一段的和，无需关注之前段的和，所以如此定义 DP 数组。

状态转移方程

有两种转移方式：

延续当前段： $dp_{i,j} = \min(dp_{i,j}, dp_{i-1,j} + a_i)$
新开一段： $dp_{i,j} = \min\limits_{k} (s_i - s_k)$ ，其中需满足 $dp_{k,j-1} \leq s_i - s_k$

优化

直接实现上述转移的时间复杂度为

O(n^3)

，无法通过全部测试点，只有整整

70

pts ~~虽然也不少了的说~~。

利用前缀和的单调递增性质，我们可以二分查找第一个合法的转移点

k

，将复杂度优化至

O(n^2 \log n)

。

输出答案

通过倒推 DP 数组，从后往前还原划分方案。
~~说人话就是寻找 DP 路径嘛。~~
还有一些细节看代码注释即可。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e3 + 10;

inline int read() {
    int x = 0, f = 0;
    char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return f ? -x : x;
}

int n, a[N], f[N][N], sum[N];
vector<int> ot;

inline int tw(int pos, int ps) { // 二分查找 
    int l = pos + 1, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sum[mid] - sum[pos] >= f[pos][ps]) {
            ans = mid, r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

signed main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i]; // 前缀和优化 
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0; // f 数组初始化 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            f[i][j] = min(f[i][j], f[i - 1][j] + a[i]);
            
            int ans = tw(i - 1, j);
            if (ans == -1) continue;
            f[ans][j + 1] = min(f[ans][j + 1], sum[ans] - sum[i - 1]);
            // 切 or 不切 
        }
    }
    int k = 0; // 返回寻找 dp 路径
    for (int i = n; i >= 1; i--) {
        if (f[n][i] <= sum[n]) {
            cout << i << endl;
            k = i;
            break;
        }
    }
    int str = n;
    while (str) {
        int tmp = f[str][k];
        ot.push_back(tmp);
        for (int j = str - 1; j >= 0; j--) {
            if (sum[str] - sum[j] == tmp) {
                str = j, k--;
                break;
            }
        }
    }
    // 因为我们是倒着存的答案所以要倒着输出()
    for (int i = ot.size() - 1; i >= 0; i--) {
        cout << ot[i] << " ";
    }
}

题解：P14597 [COCI 2025/2026 #2] 递增 / Rastući

文章操作