题意:
给定一个长度为n ( n < = 5000 )的序列,多次询问求区间[ l , r ]的两个数的异或值的最大值。
思路:
考虑O ( n 2 )的区间d p
加强版
代码:
ll a[5100],dp[5100][5100]; int main(){ int n=read,m=read; rep(i,1,n) a[i]=read; for(int i=1;i<=n;i++){ dp[i][i]=a[i]; for(int j=1;j<=n;j++) dp[i][j]=a[i]^a[j]; } for(int len=3;len<=n;len++){ for(int i=1;i+len-1<=n;i++){ int j=i+len-1; dp[i][j]=max(dp[i][j],max(dp[i+1][j],dp[i][j-1])); } } while(m--){ int l=read,r=read; cout<<dp[l][r]<<endl; } return 0; }