@[toc]

题目描述：

在这里插入图片描述
链接：https://ac.nowcoder.com/acm/problem/112798
来源：牛客网

输入描述:
在这里插入图片描述

输出描述:

Print q lines — the answers for the queries.

示例1
输入
复制

3
8 4 1
2
2 3
1 2

输出
复制

5
12

示例2
输入
复制

6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2

输出
复制

60
30
12
3

备注:

In first sample in both queries the maximum value of the function is
reached on the subsegment that is equal to the whole segment.

In second sample, optimal segment for first query are $$$$$$$$$$.

题解：

我们要先摸索出f的规律
f(i,j)=f(i,j-1) xor f(i+1,j)
dp[l][r]为区间[l,r]的最大值
dp[l][r]=max(f(l,r),dp[l][r−1],dp[l+1][r])

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5030;
ll a[maxn];
ll dp[maxn][maxn];
ll res[maxn][maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        res[i][i]=dp[i][i]=a[i];
    }
    int q;
    cin>>q;
  for (int len = 2; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      dp[l][r] = dp[l + 1][r] ^ dp[l][r - 1];
      res[l][r] = max({dp[l][r], res[l + 1][r], res[l][r - 1]});
    }
  }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        printf("%d\n",res[l][r]);
    }
    return 0;
}
/*
1 2 4 8
f(1,4)=f(1,3) xor f(2,4)
f(1,3)=f(1,2) xor f(2,3)
1 2 4
f(1 xor 2, 2 xor 4)
f(1,2)=f(1,1) xor f(2,2)
*/
//f(i,j) = f(i, j-1) xor f(i+1,j)