题解：[ABC274D] Robot Arms 2
首先提醒一下不要读错题目，因为题目并没有要求旋转 $90$ 度是顺时针还是逆时针。
将 $dx,dy$ 分开考虑，题目转换为 $dx = A_1,dy = 0$，然后 $A_{2i + 1},A_{2i} (i > 0)$ 分别对 $dx,dy$ 产生影响，问能否凑成题目所求的数 $(x,y)$。尝试 $\texttt{dp}$，若某一维的 $x$ 可以得到，那么对于本轮的 $A$，可以得到 $x - A$ 与 $x + A$，转移的时候直接枚举上一轮所有被标记的位置即可。为了方便负数的操作，直接使用 map 存储。
代码如下：
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,x,y,dx,dy,a[MAX];
map <int,int> dpx[MAX],dpy[MAX];
int main ()
{
n = read ();x = read ();y = read ();
for (int i = 1;i <= n;++i) a[i] = read ();
dpx[1][a[1]] = 1;
for (int i = 3;i <= n;i += 2)
for (auto j : dpx[i - 2])
dpx[i][j.first + a[i]] = dpx[i][j.first - a[i]] = 1;
dpy[0][0] = 1;
for (int i = 2;i <= n;i += 2)
for (auto j : dpy[i - 2])
dpy[i][j.first + a[i]] = dpy[i][j.first - a[i]] = 1;
if (dpx[(n & 1) ? n : n - 1].count (x) && dpy[(n & 1) ? n - 1 : n].count (y)) puts ("Yes");
else puts ("No");
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
