Robot Arms 2
题意
有一个长度为 \(n\) 的整数序列 \(a\) 和两个整数 \(x\) 与 \(y\)，你要在平面直角坐标系上放置 \(n + 1\) 个点(\(p_1, p_2, \cdots p_{n+1}\))，要求：
- \(p_1 = (0, 0), p_2 = (a_1, 0), p_{n+1}=(x,y)\)。
- 对于 \(1 \leqslant i \leqslant n\)，\(p_i\) 与 \(p_{i + 1}\) 的距离为 \(a_i\)。
- 对于 \(1 \leqslant i \leqslant n\)，线段 \(p_ip_{i+1}\) 与线段 \(p_{i+1}p_{i+2}\) 构成一个直角。
问：是否存在一种放点的方案满足要求，如果存在，输出 Yes；否则输出 No。
数据范围
- \(1 \leqslant n \leqslant 10^3\)。
- \(1 \leqslant a_i \leqslant 10(1 \leqslant i \leqslant n)\)。
- \(-10^4 \leqslant x, y \leqslant 10^4\)。
思路
一眼 dp，如果把坐标 \(x\) 和 \(y\) 放一起考虑，MLE 和 TLE 等着你。
线段构成直角？可以发现对于所有下标为奇数的边必然与 \(x\) 轴平行，而下标为偶数的边与 \(y\) 轴平行。
所以可以把 \(x\) 和 \(y\) 分开考虑，然后就是简单的可行性 dp 了。
注意坐标可能为负数，需要将坐标偏移。
复杂度
以下 \(V\) 表示 \(x\) 和 \(y\) 的范围的大小，即 \(2 \times 10 ^ 4\)。
- 时间：\(O(n\times V)\)。
- 空间：\(O(n + V)\)。
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10, P = 1e4, M = 510; // 注意空间
int t, n, m, x, y, z, a[M], b[M];
bool dp[N][3][3];
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> t >> x >> y >> z; // 第一条边需要特殊处理
x += P, y += P, dp[P + z][0][0] = dp[P][0][1] = 1;
for (int i = 2; i <= t; i++) {
cin >> z;
if (i % 2) {
a[++n] = z; // 存储奇数边
} else {
b[++m] = z; // 存储偶数边
}
}
for (int i = 1; i <= m; i++) { // 很显然 m >= n
for (int j = 0; j <= P * 2; j++) {
if (i <= n) {
dp[j][1][0] = 0; // 滚动数组秀操作
if (j >= a[i]) {
dp[j][1][0] = dp[j - a[i]][0][0];
}
if (j + a[i] <= 2 * P) {
dp[j][1][0] |= dp[j + a[i]][0][0];
}
}
if (i <= m) {
dp[j][1][1] = 0;
if (j >= b[i]) {
dp[j][1][1] = dp[j - b[i]][0][1];
}
if (j + b[i] <= 2 * P) {
dp[j][1][1] |= dp[j + b[i]][0][1];
}
}
}
for (int j = 0; j <= P * 2; j++) {
if (i <= n) {
swap(dp[j][1][0], dp[j][0][0]);
}
if (i <= m) {
swap(dp[j][1][1], dp[j][0][1]);
}
}
}
cout << (dp[x][0][0] && dp[y][0][1] ? "Yes" : "No"); // x 和 y 都需要满足
return 0;
}