转化题意还是很妙的，但后半部分不知道如何评价。
看到题之后，一眼会有一个直接考虑四种方向，直接 DP
的思路，显然做不得。
问题主要在于没法将两维独立开来。
这说明直接考虑
行不通，我们得考察一些性质更好的量。
考察 （即将坐标轴
45 度旋转，我也不知道出题人是怎么想到的）
如果 ，那么 和 都会加上 。
如果 ，那么 和 都会减去 。
如果 ，那么 会加 ， 会减 。
如果 ，那么 会减 ， 会加 。
容易发现，此时 要么 ，要么 ，且 的决策和
无关。
用 bitset 优化 01 背包，看看 和
是否均能被表出即可。
为了避免在背包时出现负数，我们先默认每个 都取减号，取加号时，认为其带来 的贡献。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5,S = 3.6e6 + 5;
bitset<S> f[N];
int n,d[N],sumd;
int x,y;
int ans[N];
int main()
{
cin >> n >> x >> y;
for(int i = 1;i <= n;i++) cin >> d[i],sumd += d[i];
int a = x + y,b = x - y;
if(abs(a) > sumd || abs(b) > sumd) return puts("No"),0;
if((a + sumd) & 1) return puts("No"),0;
if((b + sumd) & 1) return puts("No"),0;
a = (a + sumd) / 2;b = (b + sumd) / 2;
f[0][0] = 1;
for(int i = 1;i <= n;i++)
f[i] = f[i - 1] | (f[i - 1] << d[i]);
if(!f[n][a] || !f[n][b]) return puts("No"),0;
puts("Yes");
for(int i = n;i >= 1;i--)
{
if(!f[i - 1][a]) {ans[i] += 1;a -= d[i];}
if(!f[i - 1][b]) {ans[i] += 2;b -= d[i];}
}
for(int i = 1;i <= n;i++)
{
if(ans[i] == 0) putchar('L');
if(ans[i] == 1) putchar('U');
if(ans[i] == 2) putchar('D');
if(ans[i] == 3) putchar('R');
}
return 0;
return 0;
}
|