AcWing 2721. K-单调 题解

题目分析

本题定义了严格单调递增、严格单调递减以及(k-)单调的序列概念。给定一个整数序列和整数(k)，需要通过对序列中的元素进行加一或减一的操作，将序列转换为(k-)单调序列，求所需的最少操作数。

解题思路

本题主要通过动态规划结合左偏树的方法来求解。
1. 对原序列进行预处理，通过(v[i]=w[i] - i)和(v[i]= -w[i] - i)两种变换，分别处理递增和递减的情况。
2. 利用左偏树维护区间信息，计算将某个区间调整为单调序列的最小操作成本。
3. 通过动态规划，枚举划分的子序列个数和区间长度，计算将整个序列转换为(k-)单调序列的最少操作数。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][11], cost[N][N];
int w[N], v[N], dist[N], l[N], r[N];
struct Segment
{
    int root;
    int tot_sum, tot_size;
    int tree_sum, tree_size;

    int get_cost()
    {
        int mid = v[root];
        return mid * tree_size - tree_sum + tot_sum - tree_sum - (tot_size - tree_size) * mid;
    }
}stk[N];

• 引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于算法相关功能。
• 定义常量(N)表示序列的最大长度。
• 变量(n)表示序列的长度，(m)表示需要划分的单调子序列个数(k)。
• f[N][11]是动态规划数组，f[i][j]表示将前(i)个元素划分为(j)个单调子序列的最少操作数。
• cost[N][N]存储从第(i)个元素到第(j)个元素调整为单调序列的最小操作成本。
• w[N]存储原序列，v[N]用于存储变换后的序列。dist[N]存储左偏树节点的距离，l[N]和r[N]分别存储左偏树节点的左子节点和右子节点编号。
• 定义结构体Segment，用于维护左偏树的相关信息，包括根节点root，区间总和tot_sum、区间元素个数tot_size，左偏树节点值总和tree_sum、左偏树节点个数tree_size，以及计算该区间调整为单调序列成本的函数get_cost。

• stk[N]用于模拟栈，存储区间信息。

• 左偏树合并函数

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (v[x] < v[y]) swap(x, y);
    r[x] = merge(r[x], y);
    if (dist[l[x]] < dist[r[x]]) swap(l[x], r[x]);
    dist[x] = dist[r[x]] + 1;
    return x;
}

• 该函数用于合并两个左偏树(x)和(y)。
• 如果(x)或(y)为空，直接返回非空的那个树（若都为空则返回(0)）。
• 确保(x)的根节点值大于等于(y)的根节点值，若不满足则交换(x)和(y)。
• 将(y)合并到(x)的右子树中。
• 检查并维护左偏性质，若左子树距离小于右子树距离，则交换左右子树。
• 更新(x)的距离为其右子树距离加(1)。

• 最后返回合并后的左偏树的根节点。

• 左偏树删除根节点函数

int pop(int x)
{
    return merge(l[x], r[x]);
}

该函数用于删除左偏树(x)的根节点，通过合并其左右子树来实现，返回新的左偏树。

1. 计算区间单调化成本函数

void get_cost(int u)
{
    int tt = 0, res = 0;
    for (int i = u; i <= n; i ++ )
    {
        auto cur = Segment({i, v[i], 1, v[i], 1});
        l[i] = r[i] = 0, dist[i] = 1;
        while (tt && v[cur.root] < v[stk[tt].root])
        {
            res -= stk[tt].get_cost();
            cur.root = merge(cur.root, stk[tt].root);
            bool is_pop = cur.tot_size % 2 && stk[tt].tot_size % 2;
            cur.tot_size += stk[tt].tot_size;
            cur.tot_sum += stk[tt].tot_sum;
            cur.tree_size += stk[tt].tree_size;
            cur.tree_sum += stk[tt].tree_sum;
            if (is_pop)
            {
                cur.tree_size --;
                cur.tree_sum -= v[cur.root];
                cur.root = pop(cur.root);
            }
            tt -- ;
        }
        stk[ ++ tt] = cur;
        res += cur.get_cost();
        cost[u][i] = min(cost[u][i], res);
    }
}

• 计算从第(u)个元素开始到序列末尾的各个区间调整为单调序列的最小成本。
• 遍历从(u)到(n)的元素，对于每个位置(i)，创建一个新的区间结构体cur，表示从位置(i)开始的长度为(1)的区间，初始化相关信息。
• 当栈不为空且当前区间的根节点值小于栈顶区间的根节点值时，进行合并操作：
  • 减去栈顶区间之前计算的成本。
  • 合并当前区间的左偏树和栈顶区间的左偏树。
  • 根据区间大小的奇偶性判断是否需要删除合并后左偏树的根节点。
  • 更新当前区间的各种统计信息。
  • 弹出栈顶元素。

• 将当前区间结构体入栈，加上当前区间的成本，并更新cost[u][i]为较小值。

• 主函数

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    memset(cost, 0x3f, sizeof cost);
    for (int i = 1; i <= n; i ++ ) v[i] = w[i] - i;
    for (int i = 1; i <= n; i ++ ) get_cost(i);
    for (int i = 1; i <= n; i ++ ) v[i] = -w[i] - i;
    for (int i = 1; i <= n; i ++ ) get_cost(i);

• 读取序列长度(n)和需要划分的单调子序列个数(m)。
• 读取原序列w[i]。
• 初始化cost数组为较大值。
• 对序列进行第一次变换v[i]=w[i] - i，计算各个区间调整为递增单调序列的成本。
• 对序列进行第二次变换v[i]= -w[i] - i，计算各个区间调整为递减单调序列的成本。

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int k = 1; k <= i; k ++ )
                f[i][j] = min(f[i][j], f[i - k][j - 1] + cost[i - k + 1][i]);

    printf("%d\n", f[n][m]);
    return 0;
}

• 初始化动态规划数组f为较大值，设置f[0][0] = 0。
• 通过三层循环进行动态规划：
  • 外层循环枚举序列的前(i)个元素。
  • 中层循环枚举划分的单调子序列个数(j)。
  • 内层循环枚举最后一个单调子序列的长度(k)。
  • 更新f[i][j]为较小值，f[i][j]的转移方程为f[i][j] = min(f[i][j], f[i - k][j - 1] + cost[i - k + 1][i])，表示将前(i)个元素划分为(j)个单调子序列的最少操作数，是前(i - k)个元素划分为(j - 1)个单调子序列的最少操作数加上从第(i - k + 1)个元素到第(i)个元素调整为单调序列的最小成本。
• 最后输出将整个序列转换为(k-)单调序列的最少操作数f[n][m]。

时间复杂度分析

• 读入数据的时间复杂度为(O(n))。
• 计算区间单调化成本的函数get_cost中，对于每个起始位置(u)，内部循环的时间复杂度为(O(n))，总共调用(n)次，所以这部分时间复杂度为(O(n^2))。
• 动态规划部分，三层循环的时间复杂度为(O(n^2k))，因为(k\leq min(n, 10))，所以这部分时间复杂度也为(O(n^2))。
• 总体时间复杂度为(O(n^2))。

空间复杂度分析

主要空间消耗在于存储序列的数组、左偏树的相关数组、动态规划数组以及模拟栈的结构体数组，空间复杂度为(O(n^2 + nk))，因为(k\leq min(n, 10))，所以空间复杂度近似为(O(n^2))。