P2501 数字序列

P2501 数字序列

题意：

给出一个长度为 \(n\) 的整数序列，要求其变成一个单调严格上升的序列，但是不希望改变太多的树，也不希望改变的幅度太大。

求需要改变的最少个数，以及基础最少个数的情况下，每个数改变的绝对值之和的最小值。

思路:
推荐：https://www.luogu.com.cn/blog/luckyblock/solution-p2501

实现:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e4 + 5, INF = 1e9 + 5;
int b[N], c[N];    // a[i] - i;
int mmin[N];       // 长度为 i 的最长不下降的最小结尾
int f[N];          // 以 i 结尾最长不下降长度
ll g[N];           // 最后一位是 bi 时单调不下降的代价
ll pre[N];         // 记录前缀和
ll suf[N];         // 记录后缀和
vector<int> ed[N]; // 记录长度为 i 的最长不下降子序列的结尾
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        b[i] = x - i;
    }
    b[n + 1] = INF;//这里加多一个很大的数在最后，这样最后的最长子序列一定是以b[n + 1]为结尾的
    b[0] = -INF;//注意边界处理，0可以作为任何序列的第一个点，所以要初始化一个很小值
    int cnt = 0;
    //O(nlogn)
    for (int i = 1; i <= n + 1; i++)
    {
        int l = 0, r = cnt + 1;
        while (r - l > 1)
        {
            int mid = l + (r - l) / 2;
            if (c[mid] <= b[i])
                l = mid;
            else
                r = mid;
        }
        if (l == cnt)
            cnt++;
        f[i] = l + 1;
        c[l + 1] = b[i];
        ed[f[i]].push_back(i);
    }

    ed[0].push_back(0);
    memset(g, 20, sizeof g);
    g[0] = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        // 当前序列为 f[i] 的结尾所以当前序列的前一个数字一定是序列长度为 f[i - 1] 的结尾
        int size = ed[f[i] - 1].size();
        for (int j = 0; j < size; j++)
        {
            int from = ed[f[i] - 1][j]; // 前一个数的位置
            // 判断长度为f[i - 1]的序列中的数是否是当前数字所属序列的前一个数
            if (from > i || b[from] > b[i])
                continue;

            // 记录前缀和与后缀和，枚举 k
            pre[from] = suf[i - 1] = 0; // 初始化
            for (int k = from + 1; k <= i - 1; k++)
                pre[k] = pre[k - 1] + abs(b[k] - b[from]);

            for (int k = i - 2; k >= from; k--)
                suf[k] = suf[k + 1] + abs(b[k + 1] - b[i]);

            for (int k = from; k <= i - 1; k++)
                g[i] = min(g[i], g[from] + pre[k] + suf[k]);
        }
    }
    printf("%d\n%lld\n", n - cnt + 1, g[n + 1]);
    return 0;
}