【区间DP】XOR-pyramid

布满荆棘的人生 2024-03-26 20:42 80阅读 0赞

[Problem - B - Codeforces][]

题意：

![ce934eda659b30bf3e5794265e2f9c3f.png][]

思路：

考虑区间DP

设dp\[l\]\[r\]为区间\[l,r\]中这么多子串中f(li,ri)的最大值

然后考虑转移：

dp[l][r]=max(f[l][r],max(dp[l][r-1],dp[l+1][r]));

其中f\[l\]\[r\]表示题中f函数

为什么这么转移？区间\[l,r\]的答案就是\[l,r-1\],\[l+1,r\]的最大值的并集

然后还有一个可能就是一整个区间的f值

感觉这是一种很新的区间DP的转移，以前没看到过，可以记录一下！

然后还有个问题就是f函数怎么快速求

![5ac5f16a09b7d29514bd01de4afc9977.png][]

这张图感觉就非常通俗易懂，一个类似于杨辉三角的转移方式

Code:

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=5e3+10;
    
    int n,q,l,r;
    int a[mxn],dp[mxn][mxn],f[mxn][mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int len=1;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                if(len==1) f[l][r]=a[l];
                else f[l][r]=f[l][r-1]^f[l+1][r];
            }
        }
        for(int len=1;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                if(len==1) dp[l][r]=a[l];
                else{
                    dp[l][r]=max(f[l][r],max(dp[l][r-1],dp[l+1][r]));
                }
            }
        }
        cin>>q;
        while(q--){
            cin>>l>>r;
            cout<<dp[l][r]<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - B - Codeforces]: https://codeforces.com/group/h9H2BChqey/contest/434157/problem/B
[ce934eda659b30bf3e5794265e2f9c3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/71db1e8274eb4418a8e3450b585ad9b6.png
[5ac5f16a09b7d29514bd01de4afc9977.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ac96317310514bfbabd08901608e58a1.png