问题 A: 数列区间最大值
问题 A: 数列区间最大值
时间限制: 1 Sec 内存限制: 128 MB
提交: 39 解决: 12
[提交][状态][讨论版][命题人:add_wjl][Edit] [TestData]
题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=0
题目描述
有一串含有N个数的数列，有M个询问，每个询问有两个数字X，Y，求出X到Y这段区间内的最大值。
输入
第一行为一个N和M分别表示数字的个数和询问的个数，第二行为N个数。接下来M行，每行都有两个整数X，Y。
1 <= X, Y <= 1e5
输出
输出共M行，每行输出一个数。
样例输入
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8 样例输出
5
8 思路：建一个dp[i][j],i表示从i的位置开始扫描，j表示从i开始（i也包括）往后扫描（1<<j）个数
然后直接RMQ算法，输出的时候优化一下就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1000005][30];//动态规划 ，dp[i][j],j的意思是1<<j(扫描的个数)！！ j的意思是1<<j(扫描的个数)！！ j的意思是1<<j(扫描的个数)！！ 重要的事情说3遍！！！
int a[1000005];//用于存储数字
void st_max(int m)//初始化dp
{
for (int i = 1; i <= m; i++)
{
dp[i][0] = a[i];//j位置为0时，相当于1<<0=1,所以在范围为1的区间里的最值就是a[i]
}
for (int j = 1; (1 << j) <= m; j++)
{
for (int i = 1; i + (1 << j) - 1 <= m; i++)
{
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
//这里不太好解释，就是比如i到i+(1<<j)-1个数分为2组，一组是i到 i+(1<<(j-1))-1，另一组是 i+(1<<(j-1))到i+(1<<j)-1，进行动态规划
}
}
}
int rmq_max(int l, int r)//取l到r区间里的最值
{
int k = 0;
while ((1 << (k + 1)) <= r - l + 1)k++;//找到某个k可以让2块长为（1<<k）的区间将l到r的区间完全覆盖
return max(dp[l][ k], dp[r- (1 << k)+1][ k]);//取最值
}
int main()
{
int n;
scanf("%d", &n);
int k;
scanf("%d", &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
st_max(n);
for(int i=1;i<=k;i++)//cout卡时间，剩下就是套板子
{
int xx,yy;
scanf("%d%d",&xx,&yy);
printf("%d\n",rmq_max(xx,yy));
//cout<<rmq_max(xx,yy)<<endl;
}
}
