POJ 3264 RMQ问题用dp解决

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int N = 50010;
 6 #define INF 0x3f3f3f3f
 7 int maxn[N<<1][18] , minn[N<<1][18] , a[N];
 8 
 9 void build_dp(int n)
10 {
11     memset(maxn , 0 , sizeof(maxn));
12     memset(minn , 0x3f , sizeof(minn));
13     for(int i=0 ; i<n ; i++) minn[i][0]=maxn[i][0]=a[i];
14     for(int j=1 ; (1<<(j-1))<n ; j++){
15         for(int i=0 ; i<n ; i++){
16             minn[i][j] = min(minn[i][j-1] , minn[i+(1<<(j-1))][j-1]);
17             maxn[i][j] = max(maxn[i][j-1] , maxn[i+(1<<(j-1))][j-1]);
18         }
19     }
20 }
21 
22 int get_index(int len)
23 {
24     int ans=0 , l=1;
25     while(l<len){
26         l<<=1;
27         ans++;
28     }
29     return ans-1;
30 }
31 
32 int main()
33 {
34    // freopen("a.in" , "r" , stdin);
35     int n , q , s , t;
36     while(~scanf("%d%d" , &n , &q))
37     {
38         for(int i=0 ; i<n ; i++){
39             scanf("%d" , &a[i]);
40         }
41         build_dp(n);
42         for(int i=0 ; i<q ; i++){
43             scanf("%d%d" , &s , &t);
44             s-- , t--;
45             int len=t-s+1 , maxVal=0 , minVal=INF;
46             if(s == t){
47                 maxVal = maxn[s][0];
48                 minVal = minn[s][0];
49             }else{
50                 int k=get_index(len);
51                 maxVal = max(maxn[s][k] , maxn[t-(1<<k)+1][k]);
52                 minVal = min(minn[s][k] , minn[t-(1<<k)+1][k]);
53             }
54             printf("%d
" , maxVal-minVal);
55         }
56     }
57     return 0;
58 }

原来也做过这道题，不过今天刚看完RMQ的ST算法，就用dp的方式再写了一遍

原来用线段树来解决这个问题的，但是这里并不需要节点的更新操作，只是询问，所以在这种情况下，是可以用ST算法来解决这个问题的

POJ 3264 RMQ问题 用dp解决

POJ 3264 RMQ问题用dp解决