本文主要是介绍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;
}这篇关于POJ 1769 Minimizing maximizer 动态规划 + 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
