【题解】[ABC221G] Jumping sequence

· · 题解

很好奇怎么没有题解提到复杂度更优的做法。

题目大意

有一个无限大的平面直角坐标系，初始时你在 (0,0) 处。你要走 n 步，每次需要向上/下/左/右走 d_i 的距离，不能不走，最终要走到 (A,B)。问是否有解，有解则给出方案。

### 题目分析 首先两维背包看起来不太好做，需要稍微转化一下。 不妨设最终走 $x$ 轴的集合为 $S$，走 $y$ 轴的集合为 $T$，那么题目变成给两个集合的 $d_i$ 赋上 $1$ 或 $-1$ 的权，要求两个集合的和分别为 $A$ 和 $B$，变成了一维的背包。 当然不能枚举 $S$ 和 $T$。考虑把两个集合的方案拼在一起，由于集合无交且互补，那么就得到了一个所有数和为 $A+B$ 的方案。同理，把 $T$ 集合的方案取反再拼起来，就得到了一个所有数和为 $A-B$ 的方案。 之后做法就很明了了：考虑倒过来，用背包求出一个所有数和为 $A+B$ 及 $A-B$ 的方案，把两个方案中符号相同的归到 $S$ 集合，不同的归到 $T$ 集合，这就是原问题的一个解。这其实与其他题解中所说的旋转坐标轴本质相同。 那么现在问题就变成了：给所有数赋上 $1$ 或 $-1$ 的权，构造一个和为 $C$ 的方案。假设所有数的初始权值为 $-1$，即让 $C$ 初始时加上 $\sum d_i$，操作就变成选一些数 $+2d_i$。再让 $C$ 除以二，就变成了一个 01 背包问题。 记 $D=\max d_i$。朴素的 01 背包做法时间复杂度为 $\mathcal O(n^2D)$，使用 bitset 优化即可做到 $\mathcal O(\frac{n^2D}{\omega})$。但是这还不够，我们需要更快的算法。 --- 接下来我将介绍如何将 01 背包问题做到 $\mathcal O(nD)$ 的复杂度。 首先从前往后贪心地选取物品，即找到最大的 $pos$ 使得 $sum=\sum\limits_{i=1}^{pos}{d_i} \leq C$。若 $pos=n$ 则直接判断 $sum$ 是否等于 $C$，否则将序列分为 $\leq pos$ 和 $> pos$ 两部分。 假设已经知道了最终的解，那么最终的解一定是在目前的基础上丢掉左边的一些物品，再选上右边的一些物品。定义一次操作为丢掉左边物品或选取右边物品，接下来我将说明一定存在某种操作顺序使得目前解到答案的过程中，选取的物品和 $sum$ 始终在 $(C-D,C+D]$ 范围内。 这其实很容易说明。首先一开始的 $sum$ 肯定在范围内，如果当前的 $sum \leq C$，则选取右边的物品；否则丢掉左边的物品。由于 $d_i \leq D$，所以不会超出范围。并且最终的和为 $C$，所以不会出现选完/丢完的情况。 为了方便，不妨假设是从中间断点 $pos$ 往两边操作的，于是就可以 dp 了。设 $f_{l,r,w}$ 表示目前只考虑操作 $[l,r]$ 内的位置，是否能构造出权值和为 $w$ 的方案。$w$ 的范围由上面可知是 $\mathcal O(D)$ 的。初始时 $f_{pos+1,pos,sum}=1$，答案即为 $f_{1,n,C}$。转移时只需要枚举上一步操作是从 $f_{l+1,r}$ 还是 $f_{l,r-1}$ 转移过来，以及 $l$ 和 $r$ 有没有操作。具体转移如下： - $f_{l,r,w} \leftarrow f_{l,r-1,w}

但是时间复杂度相比普通背包并没有优化。考虑重新设计 dp，设 g_{r,w} 表示要使得 f_{l,r,w}=1，l 最大是多少，没有则记为 0。

转移时还是考虑上一步从哪边转移，以及 l,r 要不要操作。具体转移如下：

从左边转移但不操作 l 的情况不需要考虑，因为 g 取的是 \max。

状态数变少了，但复杂度没变，其瓶颈在于第 3 步。注意到当 l<g_{r-1,w} 时，其会在 r-1 时就被转移，然后从第 1 步转移回来。所以只需要转移 l \geq g_{r-1,w} 即可。对于单个 w，转移的复杂度为 \mathcal O(\sum{g_{r,w}-g_{r-1,w}})=\mathcal O(n)，于是总时间复杂度为 \mathcal O(nD)。

初值为 g_{pos,sum}=pos+1，答案即为 [g_{n,C}>0]。求方案只需要记录上一步转移即可。

同理，这个做法还可以求背包最大体积。

代码

目前最优解 85ms。

#include<bits/stdc++.h>
using namespace std;
using namespace my_std;
ll n,A,B,lim=1800,d[2020],f[2020][4040],ans0[2020],ans[2020];
pair<ll,ll> lst[2020][4040];
il void upd(ll x,ll y,ll xx,ll yy,ll v){
    if(f[x][y]<v){
        f[x][y]=v;
        lst[x][y]=MP(xx,yy);
    }
}
il bl solve(ll C){
    ll pos=0,sum=0;
    fr(i,1,n){
        if((sum+d[i])<=C){
            sum+=d[i];
            pos++;
        }
        else break;
    }
    if(pos==n&&sum<C) return 0;
    fr(i,pos,n) fr(j,1,2*lim) f[i][j]=0;
    f[pos][sum-C+lim]=pos+1;
    fr(i,pos+1,n){
        fr(j,1,2*lim) upd(i,j,i-1,j,f[i-1][j]);
        fr(j,1,lim) upd(i,j+d[i],i-1,j,f[i-1][j]);
        pfr(j,2*lim,lim+1) fr(k,f[i-1][j],f[i][j]-1) upd(i,j-d[k],i,j,k);
    }
    if(!f[n][lim]) return 0;
    fr(i,1,pos) ans[i]=1;
    fr(i,pos+1,n) ans[i]=0;
    ll x=n,y=lim;
    while(x>pos){
        ll xx=lst[x][y].fir,yy=lst[x][y].sec;
        if(xx==(x-1)&&yy==(y-d[x])) ans[x]=1;
        else if(x==xx) ans[f[x][y]]=0;
        x=xx;
        y=yy;
    }
    return 1;
}
int main(){
    n=read();
    A=read();
    B=read();
    fr(i,1,n) d[i]=read();
    A+=B;
    B=A-2*B;
    fr(i,1,n) A+=d[i];
    fr(i,1,n) B+=d[i];
    if(A<0||B<0||(A%2==1)||(B%2==1)){
        pf("No");
        return 0;
    }
    A/=2;
    B/=2;
    if(!solve(A)){
        pf("No");
        return 0;
    }
    fr(i,1,n) ans0[i]=ans[i];
    if(!solve(B)){
        pf("No");
        return 0;
    }
    pf("Yes\n");
    fr(i,1,n){
        if(ans0[i]==ans[i]){
            if(!ans0[i]) pc('L');
            else pc('R');
        }
        else{
            if(!ans0[i]) pc('D');
            else pc('U');
        }
    }
}