划过天际的星辰

o51gHaboTei1 · 2022-10-26 20:37:33 · 题解

sol of ABC221G

我们考虑直接将二维平面转 45 度。

这样终点的坐标为 (x-y,x+y)，其它的所有操作都会变化：

• L(-d,0) \rightarrow L'(-d,-d)
• R(d,0) \rightarrow R'(d,d)
• U(0,d) \rightarrow U'(-d,d)
• D(0,-d) \rightarrow D'(d,-d)

你发现一个强大的转化题意：对于 x 维和 y 维我们分开确定 d 前面的符号后进行累和，看能否从 (0,0) \rightarrow (x-y,x+y)。

我们发现这个问题有点类似 dp 的存在性问题，但是还不能完全转化，于是：

• 显然写成这种形式：d_1 \pm d_2 \pm \dots d_n = C

• 等式两边同加 \sum d_i，则前面的系数变成了 0,2，然后将 2 除过去，将 C 带成 x-y,x+y，问题即可变成一个选择/不选的存在性背包问题。

使用 bitset 优化然后输出答案即可。

时空复杂度 O(\frac{n ^ 2d}{w})。

/*
先将二维坐标轴旋转 45 度，问题变成了能否只在中间添加 +- 凑出两个数 a,b。 
*/
#include "bits/stdc++.h" 
using namespace std;
const int Len = 2e3 + 5 , M = 3.6e6 + 1;
int n,m,a,b,x,y,sm,d[Len],pst[Len];
bitset<M> dp[Len];
inline int Iabs(int x){return x < 0 ? -x : x;}
int main()
{
    scanf("%d %d %d",&n,&x,&y);
    a = x - y , b = x + y;
    for(int i = 1 ; i <= n ; i ++)
    {
        scanf("%d",&d[i]);
        sm += d[i];
    }
    if(Iabs(a) > sm || Iabs(b) > sm) return puts("No") & 0;
    if((a + sm) % 2 == 1 || (b + sm) % 2 == 1) return puts("No") & 0;
    a = (a + sm) / 2 , b = (b + sm) / 2;
    dp[1][0] = 1;
    for(int i = 1 ; i <= n ; i ++) dp[i + 1] = dp[i] | (dp[i] << d[i]);
    if(dp[n + 1][a] == 0 || dp[n + 1][b] == 0) return puts("No") & 0;
    for(int i = n ; i >= 1 ; i --)
    {
        int w = 0;
        if(!dp[i][a]){a -= d[i];w += (1 << 0);}
        if(!dp[i][b]){b -= d[i];w += (1 << 1);}
        pst[i] = w;
    }
    puts("Yes");
    for(int i = 1 ; i <= n ; i ++) 
    {
        if(pst[i] == 0) putchar('L');
        if(pst[i] == 1) putchar('D');
        if(pst[i] == 2) putchar('U');
        if(pst[i] == 3) putchar('R');
    }
    return 0;
}