题意简述：
给定一个长度为 (n) 的序列 (D，)对于每一个 (i) 可以选择向一个方向走长度为 (D_i)，问是否能走到 ((A,B))。
( exttt{Data Range:} 1le nle 2000,1le D_ile 1800,|A|,|B|le 3.6 imes 10^6)。
首先把曼哈顿距离转化为切比雪夫距离 ((A,B) ightarrow(A+B,A-B))。这样我们就将 (x)，(y) 两维独立了。
对于操作，可以转化成如下形式：
- up：((0,d) ightarrow(-d,d))；
- down：((0,-d) ightarrow(d,-d))；
- left：((-d,0) ightarrow(-d,-d))；
- right：((d,0) ightarrow(d,d))。
因此，问题就转化成：
给定 (n) 个正整数 (D_i)，确定一组 ({C_i}) 使得 (sum C_i imes D_i=s)，其中 (C_iin{1,-1})。
假设 (C_i=1) 的数的和为 (a)，(C_i=-1) 的数的和为 (b)，所有数的和为 (sum)，那么就有：
[egin{aligned}
a-b&=s\
b&=a-s\
b&=sum-b-s\
2b&=sum-s
end{aligned}
]
先把 (sum-s) 为奇数的情况判掉，然后跑一遍 bitset 优化 01 背包即可。
代码：
#include <bits/stdc++.h>
#define DC int T = gi <int> (); while (T--)
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> PII;
typedef pair <LL, LL> PLL;
template <typename T>
inline T gi()
{
T x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int N = 2003, M = N << 1;
int n, a, b;
int d[N];
int sum;
bitset <3600003> f[N];
bool ans[N][2];
int main()
{
//freopen(".in", "r", stdin); freopen(".out", "w", stdout);
n = gi <int> (), a = gi <int> (), b = gi <int> ();
f[0][0] = 1;
for (int i = 1; i <= n; i+=1)
d[i] = gi <int> (), sum += d[i], f[i] = f[i - 1] | (f[i - 1] << d[i]);
int x = a + b, y = a - b;
if (x < -sum || x > sum || y < -sum || y > sum || ((sum - x) & 1) || ((sum - y) & 1)) return puts("No"), 0;
x = sum - x, y = sum - y;
x >>= 1, y >>= 1;
if (!f[n][x] || !f[n][y]) return puts("No"), 0;
int tmpx = x, tmpy = y;
for (int i = n; i >= 1; i-=1)
{
if (tmpx >= d[i] && f[i - 1][tmpx - d[i]]) ans[i][0] = false, tmpx -= d[i];
else ans[i][0] = true;
if (tmpy >= d[i] && f[i - 1][tmpy - d[i]]) ans[i][1] = false, tmpy -= d[i];
else ans[i][1] = true;
}
puts("Yes");
for (int i = 1; i <= n; i+=1)
if (ans[i][0])
{
if (ans[i][1]) cout << 'R';
else cout << 'U';
}
else
{
if (ans[i][1]) cout << 'D';
else cout << 'L';
}
return !!0;
}
启发：
- 看到曼哈顿距离，马上考虑转成切比雪夫距离，这样可以将两维问题独立。
- 要有一定的推式子能力。