CF1456E XOR-ranges

数位DP + 区间DP 的好题。

数位的形式很显然，我们需要同时限制上下界。考虑最优解的形式，对于当前位，我们会尽可能选相同的，这样就不会产生贡献。假如当前位置，所有数已经脱离上下界限制，那么接下来所有位肯定会全部选成相同的。那么我们只需要关心，哪一个数最后脱离限制。这样就相当于将原区间分离为两个子区间，能够递归解决。

根据这一点，我们很容易想到将区间 DP 与数位 DP 进行结合。我们尝试对 $l-1,r+1$ 上的数进行限制，设当前解决 $[l,r]$ 此时已全部脱离限制，我们枚举 $[l,r]$ 中最后脱离限制的数 $mid$。设计状态 $f(x,l,r,l_1,l_2,r_1,r_2)$，表示填到第 $x$ 位，$[l,r]$ 已经全部脱离限制，$l_1$ 表示限制 $l-1$ 的是上界还是下界，$l_2$ 表示 $l-1$ 是否翻转当前位，$r_1,r_2$ 同理。具体地，有两种转移：

将 $l_1,r_1$ 的限制移到上一位，并且计算当前位贡献。
枚举 $mid$ 在当前位脱离限制，递归为子问题解决。

记忆化搜索即可，时间复杂度 $\mathcal O(n^3k)$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long 
using namespace std;
const int N=50+10;
const ll INF=1e18;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,k;
ll L[N],R[N],c[N];
ll f[N][N][N][2][2][2][2];
inline void ckmin(ll &x,ll y){x=x<y?x:y;}
ll solve(int x,int l,int r,bool l1,bool l2,bool r1,bool r2)
{
    if(x>=k)return l>r?0:INF;
    ll &res=f[x][l][r][l1][l2][r1][r2];
    if(~res)return res;
    res=INF;
    bool tl=((l1?R[l-1]:L[l-1])>>x&1)^l2,tr=((r1?R[r+1]:L[r+1])>>x&1)^r2;
    ckmin(res,solve(x+1,l,r,l1,0,r1,0)+(l!=1&&r!=n&&(tl^tr)?c[x]:0));
    for(int mid=l;mid<=r;mid++)
        for(int t=0;t<2;t++)
        {
            if(!x)ckmin(res,solve(x,l,mid-1,l1,l2,t,0)+solve(x,mid+1,r,t,0,r1,r2));
            ll lim=t?R[mid]:L[mid];
            if(L[mid]<=((lim^(1ll<<x))&(~((1ll<<x)-1)))&&((lim^(1ll<<x))|((1ll<<x)-1))<=R[mid])
                ckmin(res,solve(x,l,mid-1,l1,l2,t,1)+solve(x,mid+1,r,t,1,r1,r2));
        }
    return res;
}
int main()
{
    read(n,k);
    for(int i=1;i<=n;i++)read(L[i],R[i]);
    for(int i=0;i<k;i++)read(c[i]);
    memset(f,-1,sizeof(f));
    printf("%lld\n",solve(0,1,n,0,0,0,0));
    return 0;
}