题解：P13687 【MX-X16-T5】「DLESS-3」XOR and Rockets

· · 题解

记 x 的从低到高的第 b 位为 F(x,b)。

我们分两种情况讨论，最后一个数操作和不操作。

不操作

不操作的话整个序列的值域不超过 8192，设 f_{i,j} 表示当前处理到了 i 这个位置，a_i 异或后的值是 j，直接 dp 是 O(nV^2) 的，简单优化可以做到 O(nV)。

操作

我们称区间 [l,r] 是好的当且仅当存在 x 满足 a_l\oplus x\leq \cdots \leq a_r\oplus x，然后记最小的合法的 x 为 f(l,r)。

我们用操作点将整个序列分为若干部分，显然这些部分都需要的好的，记他们分别是 [l_i,r_i](1 \leq i \leq m)。

我们记 g_i=f(l_i,r_i) \oplus 2^{1000i}。将第 i 个部分异或上 g_i，即可满足条件。这样我们就不必考虑相邻部分交界点是否递增，而只需要保证内部递增就行了。

也就是说，经过这样的转化后，每个部分都独立了。

于是问题就转移到了，如何在可接受的时间复杂度内求出每一个区间 [l,r] 是否是好的，将 a_l \sim a_r 提取出来变成一个序列 c。

对于一个区间内的相邻点 i,i+1，我们限制了 c_i\oplus x\leq c_{i+1}\oplus x。也就是说，假设 c_i 和 c_{i+1} 在第 b 位第一次出现了分歧（不同），那么这一位异或后的结果一定是 c_i 是 0，c_{i+1} 是 1。

也就是说，如果 F(c_i,b)=1，F(c_{i+1},b)=0，那么 F(x,b)=1，如果 F(c_i,b)=0，F(c_{i+1},b)=1，那么 F(x,b)=0，显然这些限制不难记录在一个数组里面，只需要看所有的限制有没有冲突就行了。

核心代码：

const int N=5010,V=8192,inf=1e17;
int n;
int a[N],b[N];
int f[N];
bool can[N][N];
signed nd[N][N];
int dp[N][V],pre[V],suf[V];
void solve()
{
  n=R;
  fo(i,1,n) a[i]=R;
  fo(i,1,n) b[i]=R;
  fo(i,1,n) fo(j,1,n) can[i][j]=0,nd[i][j]=0;
  fo(i,1,n) f[i]=inf;
  f[0]=0;
  fo(i,1,n)
  {
    can[i][i]=1,nd[i][i]=0;
    int nd0[13]={0},nd1[13]={0};
    m1(nd0,0),m1(nd1,0);
    fo(j,i+1,n)
    {
      if(a[j]>a[j-1])
      {
        rep(k,12,0) if((a[j]>>k&1)!=(a[j-1]>>k&1)){nd0[k]=1;break;}
      }
      if(a[j]<a[j-1])
      {
        rep(k,12,0) if((a[j]>>k&1)!=(a[j-1]>>k&1)){nd1[k]=1;break;}
      }
      bool flag=1;
      fo(k,0,12) flag&=(nd0[k]==0||nd1[k]==0);
      if(!flag) break;
      can[i][j]=1;
      fo(k,0,12) if(nd1[k]) nd[i][j]+=(1<<k);
      // cout<<i<<' '<<j<<' '<<nd[i][j]<<endl;
    }
  }
  fo(i,1,n) fo(j,0,i-1) if(can[j+1][i])
  {
    f[i]=min(f[i],f[j]+b[i]);
  }
  int ans1=f[n];
  fo(i,1,n) fo(j,0,V-1) dp[i][j]=1e17;
  fo(j,0,V-1) dp[n][j^a[n]]=(j!=0)*b[n];
  // cout<<dp[n][0]<<endl;
  rep(i,n,1)
  {
    if(i!=n)
    {
      fo(j,0,V-1)
      {
        int val=(a[i]^j^a[i+1]);
        fo(k,val,val) if(j<=k) dp[i][j]=min(dp[i][j],dp[i+1][k]);
        dp[i][j]=min(dp[i][j],suf[j]+b[i]);
      }
    }
    pre[0]=dp[i][0];
    fo(j,1,V-1) pre[j]=min(pre[j-1],dp[i][j]);
    suf[V-1]=dp[i][V-1];
    rep(j,V-2,0) suf[j]=min(suf[j+1],dp[i][j]);
  }
  int ans=1e17;
  fo(i,0,V-1) ans=min(ans,dp[1][i]);
  write(min(ans1,ans)),puts("");
}
void main(){
  MT solve();
}