RMQ算法
2018-06-27 10:01:25来源:未知 阅读 ()
一.概述
RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,下面介绍一下解决这两种问题的比较高效的算法。当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN),这里我们暂不介绍
二.算法思路
1.首先利用dp预处理出从i点开始往后的2^j的最大值,dp的时候将其拆分成两段
2.查询出左端点以i开始,终点以j开始的最大值
一篇非常好的博客http://blog.csdn.net/liang5630/article/details/7917702
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int a[2000001]; 7 int minn[2000001][15]; 8 int fastpow(int a,int p) 9 { 10 int base=a; 11 int ans=1; 12 while(p) 13 { 14 if(p%2)ans*=base; 15 base*=base; 16 p/=2; 17 } 18 return ans; 19 } 20 int main() 21 { 22 int n,m; 23 scanf("%d%d",&n,&m); 24 for(int i=0;i<=n;i++) 25 for(int j=0;j<=14;j++) 26 minn[i][j]=0x7ff; 27 for(int i=1;i<=n;i++) 28 scanf("%d",&minn[i][0]);// 第i个点跳1步能到达的点是其本身 29 for(int j=0;j<=14;j++)// 2^j 30 { 31 for(int i=1;i<=n;i++)// 根据dp的无后效性,要在j一定的情况下把每一个点跳完之后能到达的位置处理出来 32 { 33 if(i+(1<<j)-1<=n)// 第二段区间保证在范围之内 34 minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j]); 35 } 36 } 37 // 三段区间 i——i+2^(j-1)-1——i+2^j-1 38 printf("0\n"); 39 int k=log(m)/log(2);// 保证求值区间的长度在要求的范围之内 40 // 带求区间 i-m to i 41 for(int i=2;i<=n;i++) 42 { 43 printf("%d\n",min(minn[i-m][k],minn[i-fastpow(2,k)+1][k])); 44 // 左端点 右端点 45 } 46 return 0; 47 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:tarjan算法详解
下一篇:P3390 【模板】矩阵快速幂
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash