Title: 延綿的山峰 傳送門
Input: climb.in
Output: climb.out
Time Limit: 1000 ms
Memory Limit: 128 MB
Level: ★★
問題描述
有一座延綿不斷、跌宕起伏的山，最低處海拔為0，最高處海拔不超過8848米，從這座山的一端走到另一端的過程中，每走1米海拔就升高或降低1米。有Q個登山隊計劃在這座山的不同區段登山，當他們攀到各自區段的最高峯時，就會插上隊旗。請你寫一個程序找出他們插旗的高度。
輸入文件
第1行，一個整數N(N<=10^6)，表示山兩端的跨度。
接下來N+1行，每行一個非負整數Hi，表示該位置的海拔高度，其中H0=Hn=0。
然後是一個正整數Q(Q<=7000)，表示登山隊的數量。
接下來Q行，每行兩個數Ai, Bi，表示第i個登山隊攀爬的區段[Ai,Bi]，其中0<=Ai<=Bi<=N。
輸出文件
Q行，每行為一個整數，表示第i個登山隊插旗的高度。
樣例輸入
10
0
1
2
3
2
3
4
3
2
1
0
5
0 10
2 4
3 7
7 9
8 8
樣例輸出
4
3
4
3
2
【分析】
看到題，我首先花了五分鐘敲了一個暴力的代碼，竟然還過8組測試數據！
這題是RMQ問題，也就是區間最值問題。這題一般是用線段樹（又稱“區間樹”） 做的，但是我沒有用線段樹做，用的是ST算法。
ST算法是“分治/二分”的思想，使用了動態規劃。
RMQ(Range Minimum/Maximum Query)問題是求區間最值問題。可以寫一個線段樹，但是預處理和查詢的複雜度都是O（logn)。這裡有更牛的演算法，就是ST演算法，它可以做到O(nlogn)的預處理，O(1)地回答每個詢問。
來看一下ST演算法是怎麼實現的(以最大值為例）：
首先是預處理，用一個DP解決。設a[i]是要求區間最值的數列，f[i,j]表示從第i個數起連續2^j個數中的最大值。例如數列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1個數起，長度為2^0=1的最大值，其實就是3這個數。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……從這裡可以看出f[i,0]其實就等於a[i]。這樣，Dp的狀態、初值都已經有了，剩下的就是狀態轉移方程。我們把f[i，j]平均分成兩段（因為f[i，j]一定是偶數個數字），從i到i+2^(j-1)-1為一段，i+2^(j-1)到i+2^j-1為一段(長度都為2^（j-1）)。用上例說明，當i=1，j=3時就是3,2,4,5 和 6,8,1,2這兩段。f[i，j]就是這兩段的最大值中的最大值。於是我們得到了動規方程F[i,j]=max（F[i，j-1],F[i+2^(j-i)，j-1]）.
接下來是得出最值，也許你想不到計算出f[i，j]有什麼用處，一般毛想想計算max還是要O(logn)，甚至O(n)。但有一個很好的辦法，做到了O（1）。還是分開來。如在上例中我們要求區間[2，8]的最大值，就要把它分成[2,5]和[5,8]兩個區間，因為這兩個區間的最大值我們可以直接由f[2，2]和f[5，2]得到。擴展到一般情況，就是把區間[l，r]分成兩個長度為2^n的區間（保證有f[i，j]對應）。直接給出運算式：f[i,j] 表示 從第 i 個數數 2^j 中最小的數。那麼：
最大值 f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]);
最小值 f[i,j]=min(f[i,j-1],f[i+2^(j-1),j-1]);
【我的代碼】
C++语言: Codee#25395
01 /*
02 *Problem: 延綿的山峰 climb
03 *Author: Yee-fan Zhu
04 *Method: ST-Algoritm/Dynamic Programming
05 *GTalk: zyfworks@gmail.com
06 *Website:http://yeefanzhu.blogspot.com/
07 */
08 #include <cstdio>
09 #include <iostream>
10 #include <cstdlib>
11 #include <cmath>
12 using namespace std;
13
14 int MAX(int a,int b)
15 {
16 return a>b?a:b;
17 }
18
19 const int MAXN=1000003;
20 const int MAX_INDEX=10;
21 int N,Q;
22 int Max[MAXN][MAX_INDEX];
23 int Num[MAXN];
24
25 void init()
26 {
27 scanf("%d\n",&N);
28 N++;
29 for (int i=1;i<=N;i++)
30 scanf("%d\n",&Num[i]),
31 Max[i][0]=Num[i];
32 scanf("%d\n",&Q);
33
34 int M=int(floor(log((double)N)/log(2.0)));
35 for (int i=1;i<=M;i++)
36 {
37 for (int j=N;j>=1;j--)
38 {
39 Max[j][i]=Max[j][i-1];
40 if(j+(1<<(i-1))<=N )
41 Max[j][i]=MAX(Max[j][i],Max[j+(1<<(i-1))][i-1]);
42 }
43 }
44 }
45
46 int RMQ(int l,int r)
47 {
48 int m=int (floor(log((double)(r-l+1))/log(2.0)));
49 int a=MAX(Max[l][m],Max[r-(1<<m)+1][m]);
50 return a;
51 }
52
53 int main()
54 {
55 freopen("climb.in","r",stdin);
56 freopen("climb.out","w",stdout);
57 init();
58 int a,b;
59 for (int i=1;i<=Q;i++)
60 {
61 scanf("%d %d\n",&a,&b);
62 a++,b++;
63 printf("%d\n",RMQ(a,b));
64 }
65 return 0;
66 }
02 *Problem: 延綿的山峰 climb
03 *Author: Yee-fan Zhu
04 *Method: ST-Algoritm/Dynamic Programming
05 *GTalk: zyfworks@gmail.com
06 *Website:http://yeefanzhu.blogspot.com/
07 */
08 #include <cstdio>
09 #include <iostream>
10 #include <cstdlib>
11 #include <cmath>
12 using namespace std;
13
14 int MAX(int a,int b)
15 {
16 return a>b?a:b;
17 }
18
19 const int MAXN=1000003;
20 const int MAX_INDEX=10;
21 int N,Q;
22 int Max[MAXN][MAX_INDEX];
23 int Num[MAXN];
24
25 void init()
26 {
27 scanf("%d\n",&N);
28 N++;
29 for (int i=1;i<=N;i++)
30 scanf("%d\n",&Num[i]),
31 Max[i][0]=Num[i];
32 scanf("%d\n",&Q);
33
34 int M=int(floor(log((double)N)/log(2.0)));
35 for (int i=1;i<=M;i++)
36 {
37 for (int j=N;j>=1;j--)
38 {
39 Max[j][i]=Max[j][i-1];
40 if(j+(1<<(i-1))<=N )
41 Max[j][i]=MAX(Max[j][i],Max[j+(1<<(i-1))][i-1]);
42 }
43 }
44 }
45
46 int RMQ(int l,int r)
47 {
48 int m=int (floor(log((double)(r-l+1))/log(2.0)));
49 int a=MAX(Max[l][m],Max[r-(1<<m)+1][m]);
50 return a;
51 }
52
53 int main()
54 {
55 freopen("climb.in","r",stdin);
56 freopen("climb.out","w",stdout);
57 init();
58 int a,b;
59 for (int i=1;i<=Q;i++)
60 {
61 scanf("%d %d\n",&a,&b);
62 a++,b++;
63 printf("%d\n",RMQ(a,b));
64 }
65 return 0;
66 }
沒有留言:
張貼留言