CF1456E XOR-ranges 做题记录

给定 $n$ 和 $k$，有 $n$ 个 $< 2^k$ 的非负整数变量 $x_1,x_2,\dots,x_n$，其中 $x_i$ 的取值范围是 $[l_i,r_i]$。

给出数列 $c_0,c_1,\dots,c_{K-1}$，并由此定义一个代价函数 $f(x)$：

$f(x)=\sum_{i=0}^{k-1}(\lfloor\tfrac x{2^i}\rfloor\bmod 2)\cdot c_i$

确定每个变量的取值，使得 $\sum_{i=2}^nf(x_i\oplus x_{i-1})$ 最小，输出该最小值。

$2\le n\le50$，$1\le k\le50$，$0\le l_i\le r_i< 2^k$，$0\le c_i\le10^{12}$。

考虑二进制意义下从高往低一位一位填，若当前填到了第 $p$ 位且 $x_{[l,r]}$ 之后的位无论怎么填都不会超出 $[l_i,r_i]$ 的限制，则 $x_{[l,r]}$ 后面的位可以贪心地和 $x_{l-1}$ 一样，所以 $x_{[l,r]}$ 可以删掉。

不妨能删就删，即钦定 $x_{l-1}$ 和 $x_{r+1}$ 的高 $p$ 位都顶着上界和下界中的至少一个。

那么有一个朴素的 dp，设 $f_{p,l,r,0/1,0/1}$ 表示填完高 $p$ 位，删掉了区间 $x_{[l,r]}$，$x_{l-1}$ 顶到上界/下界，$x_{r+1}$ 顶到上界/下界。

发现这样转移不了，因为若 $x_k$ 在第 $p$ 位时解除了限制，则它的第 $p$ 位需要翻转。不妨把这个东西加入状态，设 $f_{p,l,r,0/1,0/1,0/1,0/1}$ 表示填完高 $p$ 位，删掉了区间 $x_{[l,r]}$；$x_{l-1}$ 顶到上界/下界，是否在第 $p$ 位解除限制；$x_{r+1}$ 顶到上界/下界，是否在第 $p$ 位解除限制。

注意这样设计状态后 $f_{*,*,*,*,0,*,0}$ 才是我们想要的东西，$f_{*,*,*,*,1,*,*}$ 和 $f_{*,*,*,*,*,*,1}$ 只是中间状态。

转移较为简单，注意到 $f_{p,l,r,*,*,*,*}$ 只有两个来源，即 $f_{p+1,l,r,*,0,*,0}+\text{第 }p\text{ 位的代价}$ 和 $f_{p,l,k-1,*,*,*,1}+f_{p,k+1,r,*,1,*,*}$。前者对应 $x_{[l,r]}$ 没有在第 $p$ 位解除限制的变量，后者则对应有这样的变量。

注意 $p=0$ 时后面没有位了，要特判。

时间复杂度 $O(kn^3)$，使用记忆化搜索实现会简洁很多，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int S=55;
const long long inf=1e18;

int n,m;
long long L[S],R[S],c[S];
long long f[S][S][S][2][2][2][2];

inline void tom(long long &x,long long y){x=min(x,y);}

long long g(int p,int l,int r,int l0,int l1,int r0,int r1)
{
	if(p==m) return l>r?0:inf;
	long long &u=f[p][l][r][l0][l1][r0][r1];
	if(u!=-1) return u;
	int stl=(((l0==0?L[l-1]:R[l-1])>>p)&1)^l1;
	int str=(((r0==0?L[r+1]:R[r+1])>>p)&1)^r1;
	u=inf;
	tom(u,g(p+1,l,r,l0,0,r0,0)+(l!=1&&r!=n&&stl!=str)*c[p]);
	for(int k=l;k<=r;k++)
	{
		for(int t=0;t<=1;t++)
		{
			if(p==0) tom(u,g(p,l,k-1,l0,l1,t,0)+g(p,k+1,r,t,0,r0,r1));
			long long vk=(t==0?L[k]:R[k])^(1ll<<p);
			if((vk&(~((1ll<<p)-1)))>=L[k]&&(vk|((1ll<<p)-1))<=R[k])
			{
				tom(u,g(p,l,k-1,l0,l1,t,1)+g(p,k+1,r,t,1,r0,r1));
			}
		}
	}
	return u;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&L[i],&R[i]);
	for(int i=0;i<=m-1;i++) scanf("%lld",&c[i]);
	memset(f,-1,sizeof(f));
	printf("%lld\n",g(0,1,n,0,0,0,0));
	return 0;
}