首页 > 其他 > 详细

51nod1174(RMQ)

时间:2016-12-29 07:16:59      阅读:205      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1174

 

题意:中文题诶~

 

思路:RMQ模板题

 关于RMQ: http://blog.csdn.net/liang5630/article/details/7917702

 

代码:

 1 #include <bits/stdc++.h>
 2 #define MAXN 10010
 3 using namespace std;
 4 
 5 int dp[MAXN][30], a[MAXN]; //dp[i][j]存储从下标i开始,长度为2^j区间的最大值
 6 
 7 int main(void){
 8     int n;
 9     scanf("%d", &n);
10     for(int i=0; i<n; i++){
11         scanf("%d", &a[i]);
12         dp[i][0]=a[i];    //dp初始化
13     }
14     int len=log2(n);
15     for(int j=1; j<=len; j++){ //长度为2^j的区间最大值可以由相邻的两个长度为2^(j-1)的区间合成
16         for(int i=0; i<n; i++){
17             if(i+(1<<j)<=n){
18                 dp[i][j]=max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); //从相邻两个区间中选取最大值
19             }
20         }
21     }
22     int m;
23     scanf("%d", &m);
24     while(m--){
25         int s, e;
26         scanf("%d%d", &s, &e);
27         int cnt=log2(e-s+1);
28         cout << max(dp[s][cnt], dp[e-(1<<cnt)+1][cnt]) << endl;
29     }
30     return 0;
31 }

 

51nod1174(RMQ)

原文:http://www.cnblogs.com/geloutingyu/p/6230784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!