首页 > 代码库 > POJ 1769 Minimizing maximizer（DP+zkw线段树）
POJ 1769 Minimizing maximizer（DP+zkw线段树）
【题目链接】 http://poj.org/problem?id=1769
【题目大意】
给出一些排序器，能够将区间li到ri进行排序，排序器按一定顺序摆放
问在排序器顺序不变的情况下，一定能够将最大值交换到最后一位至少需要保留几个排序器
【题解】
我们发现，对于每个排序器，dp[ri]=min(dp[ri],min(dp[li]~dp[ri-1])+1)
我们用线段树对dp值进行最小值维护，顺序更新即可。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>#include <climits>using namespace std;const int N=50010;int T[N*4],n,m,M,l,r,x,y;int main(){ while(~scanf("%d%d",&n,&m)){ for(M=1;M<n;M<<=1); fill(T,T+M+n+1,INT_MAX/2); T[M+1]=0; while(m--){ scanf("%d%d",&l,&r); if(l<r){ int t=INT_MAX/2; x=l+M-1; y=r+M; while(x^y^1>0){ if(~x&1)t=min(t,T[x+1]); if(y&1)t=min(t,T[y-1]); x>>=1;y>>=1; }T[M+r]=min(T[M+r],t+1); for(x=(M+r)/2;x;x/=2)T[x]=min(T[x<<1],T[(x<<1)^1]); } }printf("%d\n",T[n+M]); }return 0;}POJ 1769 Minimizing maximizer（DP+zkw线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。