AtCoder Beginner Contest 221（G - Jumping sequence）思维+bitset

传送门

题解

官方题解很清楚了，这题巧妙的地方在于将坐标轴旋转45度，使得每次坐标移动可以对X、Y两个坐标造成绝对值相同的影响，从而建立联系。

代码

/*************************************************************************
	> File Name: 1.cpp
	> Author: Knowledge_llz
	> Mail: 925538513@qq.com 
	> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
	> Created Time: 2021/10/3 12:25:05
 ************************************************************************/

#include
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define LL long long
#define pb push_back
#define fi first
#define se second
#define pr pair
#define mk(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
int n, sum = 0, a, b, d[2021], s[2021], t[2021];
bitset<3600001> bit[2001];
char str[] = {'L', 'D', 'U', 'R'};
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	cin >> n >> a >> b;
	for(int i = 1; i <= n; ++i){
		cin >> d[i];
		sum += d[i];
	}
	if((sum + a + b) < 0 || (sum + a + b) & 1 || (sum + a + b) / 2 > sum){
		cout << "No" << endl;
		return 0;
	}
	if((sum + a - b) < 0 || (sum + a - b) & 1 || (sum + a - b) / 2 > sum){
		cout << "No" << endl;
		return 0;
	}
	bit[0].set(0);
	for(int i = 1; i <= n; ++i) bit[i] = bit[i - 1] | (bit[i - 1] << d[i]);
	if(bit[n][(sum + a + b) / 2] == 0 || bit[n][(sum + a - b) / 2] == 0){
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	int x = (sum + a + b) / 2;
	for(int i = n; i >= 1; --i){
		if(bit[i - 1][x]) t[i] = 0;
		else{ x -= d[i]; t[i] = 1; }
	}
	x = (sum + a - b) / 2;
	for(int i = n; i >= 1; --i){
		if(bit[i - 1][x]) s[i] = 0;
		else{ x -= d[i]; s[i] = 1; }
	}
	for(int i = 1; i <= n; ++i){
		int val = t[i] * 2 + s[i];
		cout << str[val];
	}
	return 0;
}