POJ 1769 Minimizing maximizer 动态规划 + 线段树

一、题目大意

maximizer是一个排序的软件，可以输出 n 个数字中最大的那个。

它实现的思路是基于多个排序器形成的管道，第一个排序器排序的输出交给第二个排序器，第二个排序器进行排序的输出交给第三个排序器，最终第n个排序器排好后的最后一个元素就是源输入中最大的那个。

每个排序器的可以对输入的数列的一部分区间进行排序，其余部分不做处理。

观察得知，maximizer去掉部分的排序器仍然可以正确输出最大的数字，题目要求得出需要的最小的排序器的数量。

二、解题思路

我们不难看出，进行多次区间排序，最终要让最大的元素排在最后，那么这次些区间一定可以覆盖?1 到 n 的全部范围，且这些区间必须按序。

例如对40个数字进行处理，则区间排序顺序可以为[1,10],[10,20],[20,30],[30,40]，四次排序过后，最大的元素会被排在最后。

那么本题目类似于找到一个最短的，能够覆盖1 到 n 的上升子序列。

求上升子序列不难想到用动态规划，可以定义一个 n? 大小的数组，dp[N]。

dp[i]代表将 [1,i] 的区间全部排序所需的最小的排序器数量。

程序开始时，将dp[1]设置为0，循环读入每个区间 L,R，循环内执行操作

1、找出 dp[L]到dp[R]的最小值 pre（将[1,L]的位置排好序的最小消耗）

2、找出 dp[R]当前的值 crt

如果 pre + 1 < crt，则 更新 dp[R]位置为 pre + 1（将[1,R]的位置排好序的最小消耗）

最终输出 dp[N]位置的值即可

因为需要找出 dp[L]到dp[N]的最小值，所以dp数组可以用线段树实现，更新值的时候同步更新父节点，便于区间内快速找最值。

（我为了方便，代码让有效数组都从0开始，且区间都为左闭右开）

三、代码

#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int dat[131072];
int n, m;
void init()
{
    for (int i = 0; i < 131072; i++)
    {
        dat[i] = m;
    }
}
int query(int _l, int _r, int i, int l, int r)
{
    if (_l >= r || _r <= l)
    {
        return INF;
    }
    else if (l >= _l && r <= _r)
    {
        return dat[i];
    }
    else
    {
        int lch = query(_l, _r, i * 2 + 1, l, (l + r) / 2);
        int rch = query(_l, _r, i * 2 + 2, (l + r) / 2, r);
        return min(lch, rch);
    }
}
void update(int x, int v, int i, int l, int r)
{
    if (x >= r || x < l)
    {
    }
    else if (l == x && r == x + 1)
    {
        dat[i] = v;
        int p = i;
        while (p > 0)
        {
            p = (p - 1) / 2;
            dat[p] = min(dat[p * 2 + 1], dat[p * 2 + 2]);
        }
    }
    else
    {
        update(x, v, i * 2 + 1, l, (l + r) / 2);
        update(x, v, i * 2 + 2, (l + r) / 2, r);
    }
}
void solve()
{
    int i, j;
    scanf("%d%d", &n, &m);
    init();
    update(0, 0, 0, 0, n);
    for (int k = 0; k < m; k++)
    {
        scanf("%d%d", &i, &j);
        int v = query(i - 1, j, 0, 0, n);
        int crt = query(j - 1, j, 0, 0, n);
        if (v + 1 < crt)
        {
            update(j - 1, v + 1, 0, 0, n);
        }
    }
    printf("%d\n", query(n - 1, n, 0, 0, n));
}
int main()
{
    solve();
    return 0;
}