题目链接:https://cn.vjudge.net/problem/HRBUST-1188
每一次按照二进制的方式进行更新,二维数组dp [i] [j],i表示下标,j表示从i 开始的往后移动2的j-1次方个数再-1.
AC代码:
#include<iostream>
#include<cmath>
#include<stack>
#include<iomanip>
#include<queue>
#include<cstring>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
# define inf 0x3f3f3f3f
# define ll long long
const int maxn = +;
int dp[maxn][];
int n;
void RMQ()
{
for(int i=; i<=; i++)
{
for(int j=; j<=n; j++)
{
if(j+(<<i)-<=n)
{
dp[j][i]=max(dp[j][i-],dp[j+(<<(i-))][i-]);
}
}
}
}
int main()
{ int Case=;
while(~scanf("%d",&n))
{
memset(dp,,sizeof(dp));
for(int i=; i<=n; i++)
{
scanf("%d",&dp[i][]);
}
RMQ();
int m;
int t1,t2;
scanf("%d",&m);
printf("Case %d:\n",++Case);
while(m--)
{
scanf("%d%d",&t1,&t2);
int k=;
// k=(int)(log((double)(t2-t1+1))/log(2.0));
while((t1+<<(k+))<=t2)k++;
printf("%d\n",max(dp[t1][k],dp[t2-(<<k)+][k]));
}
}
return ;
}