题目链接

Atcoder方向
Luogu方向

题目解法

因为上下左右是对横纵坐标分别修改的，不好操作，考虑如何只考虑一维限制
考虑一个重要套路：将坐标轴旋转 $45°$，这样终点坐标会变为 $A+B,A-B$
然后对横纵坐标分开做背包，然后记录方案即可
可以发现 $dp$ 过程可以用 $bitset$ 优化，所以时间复杂度 $O(\frac{n^{2}d}{\omega })$

#include <bits/stdc++.h>
using namespace std;
const int N(2010),D(1810);
int n,A,B,tA,tB,d[N];
bitset<N*D> bs[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
int main(){n=read(),tA=read(),tB=read();A=tA+tB,B=tA-tB;int tot=0;for(int i=1;i<=n;i++) d[i]=read(),tot+=d[i];reverse(d+1,d+n+1);if(((A+tot)&1)||((B+tot)&1)){ puts("No");exit(0);}if(A+tot<0||B+tot<0||A>tot||B>tot){ puts("No");exit(0);}bs[0][0]=1;for(int i=1;i<=n;i++) bs[i]=bs[i-1]|(bs[i-1]<<d[i]);if(!bs[n][(A+tot)/2]||!bs[n][(B+tot)/2]){ puts("No");exit(0);}puts("Yes");int cur1=(A+tot)/2,cur2=(B+tot)/2;for(int i=n;i>=1;i--){bool f1=0,f2=0;if(cur1>=d[i]&&bs[i-1][cur1-d[i]]) cur1-=d[i],f1=1;if(cur2>=d[i]&&bs[i-1][cur2-d[i]]) cur2-=d[i],f2=1;
//		cout<<cur1<<' '<<cur2<<' '<<f1<<' '<<f2<<'\n'; if(f1&&f2) putchar('R');if(f1&&!f2) putchar('U');if(!f1&&f2) putchar('D');if(!f1&&!f2) putchar('L'); }return 0;
}