題干：

給出一個有N個數(shù)的序列，編號0 - N - 1。進行Q次查詢，查詢編號i至j的所有數(shù)中，最大的數(shù)是多少。

例如: 1 7 6 3 1。i = 1, j = 3，對應(yīng)的數(shù)為7 6 3，最大的數(shù)為7。（該問題也被稱為RMQ問題）

?收起

輸入

第1行：1個數(shù)N，表示序列的長度。(2 <= N <= 10000) 第2 - N + 1行：每行1個數(shù)，對應(yīng)序列中的元素。(0 <= S[i] <= 10^9) 第N + 2行：1個數(shù)Q，表示查詢的數(shù)量。(2 <= Q <= 10000) 第N + 3 - N + Q + 2行：每行2個數(shù)，對應(yīng)查詢的起始編號i和結(jié)束編號j。(0 <= i <= j <= N - 1)

輸出

共Q行，對應(yīng)每一個查詢區(qū)間的最大值。

輸入樣例

5 1 7 6 3 1 3 0 1 1 3 3 4

輸出樣例

7 7 3

解題報告：

? 板子。

AC代碼：

#include<bits/stdc++.h>using namespace std; int dp[1000005][25]; int qq[10005]; int a[10005]; int n,q; void init() {for(int i = 1; i<=n; i++) dp[i][0] = a[i];for(int j = 1; (1<<j) <= n; j++) {//也可以for(int j = 1; n>>j > 0; j++) {這兩個其實是等價的？for(int i = 1; i+(1<<j)-1 <= n; i++) {dp[i][j] = max(dp[i][j-1] , dp[i + (1<<(j-1))][j-1]);}}for(int i = 1; i<=n; i++) {int k = 0;while(1<<(k+1) <= i) k++;qq[i] = k;} } int cal(int l,int r) {int k = qq[r-l+1];return max(dp[l][k],dp[r- (1<<k) + 1][k]); } int main() {scanf("%d",&n);for(int i = 1 ;i<=n; i++) {scanf("%d",&a[i]);}init();scanf("%d",&q);while(q--) {int ll,rr;scanf("%d%d",&ll,&rr);printf("%d\n",cal(ll+1,rr+1));}return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【51nod - 1174 】区间中最大的数（RMQ问题，ST表，模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。