I love max and multiply 题解(二进制dp)

题目链接

题目思路

这个不知道叫啥感觉算是个二进制dp把

设\(n\)为化简为\(2\)进制的最高位数

我最开始是直接\(3^n\)枚举子集，但是喜提\(TLE\)

标准是\(n\times2^n\)

每次枚举只枚举比他多一个1的元素，然后从大到小for过去就能得到答案

因为比他多一个1的元素也枚举了比他多一个1的元素，递归的思路，这样其实相当于枚举了他的所有父亲

注意有负数

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=6e5+5,inf=0x3f3f3f3f,mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n;
ll dp1[maxn][2],dp2[maxn][2];
ll ans[maxn];
int main(){
    int _; scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=0,a;i<=n-1;i++){
            scanf("%d",&a);
            dp1[i][0]=dp1[i][1]=a;
        }
        for(int i=0,b;i<=n-1;i++){
            scanf("%d",&b);
            dp2[i][0]=dp2[i][1]=b;
        }
        int m=1;
        while(m<n-1) m=(m<<1);
        for(int i=0;i<=19;i++){
            for(int j=m-1;j>=0;j--){
                if((!(j&(1<<i)))&&j<=n-1&&(j^(1<<i))<=n-1){
                    dp1[j][0]=min(dp1[j^(1<<i)][0],dp1[j][0]);
                    dp1[j][1]=max(dp1[j^(1<<i)][1],dp1[j][1]);
                    dp2[j][0]=min(dp2[j^(1<<i)][0],dp2[j][0]);
                    dp2[j][1]=max(dp2[j^(1<<i)][1],dp2[j][1]);
                }
            }
        }
        ans[n]=-INF;
        ll pr=0;
        for(int i=n-1;i>=0;i--){
            ans[i]=max(max(dp1[i][0]*dp2[i][0],dp1[i][0]*dp2[i][1]),max(dp1[i][1]*dp2[i][0],dp1[i][1]*dp2[i][1]));
            ans[i]=max(ans[i],ans[i+1]);
            pr=(pr+ans[i])%mod;
        }
        printf("%lld\n",(pr%mod+mod)%mod);
    }
    return 0;
}