题意:
定义一个函数 f(a):
给出一个数组 a, 有 q 个询问, 每次询问回答在 l 到 r 的区间内, 连续子串的 f 函数的最大值.
思路:
画图, 来自 codeforces http://codeforces.com/profile/SheepRanger
由此图可知, f(l,r) = f(l,r-1) ^ f(l+1,r), 多画图哇!
所以就变成了区间 dp, 同时维护 f(l,r) 与 ans(l,r):
f[l][r] = f[l][r-1] ^ f[l+1][r]
ans[l][r] = max(f[l][r],ans[l][r-1],ans[l+1][r]).
代码:
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- const int N = 5005;
- int dp[N][N];
- int a[N];
- int ans[N][N];
- int main()
- {
- int n;
- scanf("%d",&n);
- for (int i = 0;i <n;i++) scanf("%d",&a[i]);
- for (int i = 0;i < n;i++) dp[i][i] = ans[i][i] = a[i];
- for (int i = 1;i < n;i++)
- {
- for (int j = 0;j < n;j++)
- {
- int l = j,r = j+i;
- if (r>= n) break;
- //if (l == 0 && r == 5) puts("gg");
- dp[l][r] = dp[l][r-1] ^ dp[l+1][r];
- ans[l][r] = max(ans[l][r-1],ans[l+1][r]);
- ans[l][r] = max(ans[l][r],dp[l][r]);
- }
- }
- int q;
- scanf("%d",&q);
- while (q--)
- {
- int l,r;
- scanf("%d%d",&l,&r);
- l--,r--;
- printf("%d\n",ans[l][r]);
- }
- return 0;
- }
来源: https://www.cnblogs.com/kickit/p/9048837.html